Find score of array after marking all elements

XXX. Score Descending Sequences

Array

Sequence

Key Points:

• **Sequence Properties**:
  • Process array in pairs starting from even indices
  • Look for descending sequences
  • Take alternating numbers from sequences
• **Algorithm Flow**:
  • Start at even indices
  • Extend sequence while descending
  • Process sequence backwards for correct alternation

Example:

For array [7,2,3,4,5,6]:

• First sequence: [7,2] → Take 7
• Second sequence: [3] → Take 3
• Third sequence: [5] → Take 5
• Final score = 15

Java Implementation:

public long findScore(int[] numbers) {
    long ans = 0;                  // Use long to prevent overflow
    
    // Process array in pairs (even indices)
    for (int i = 0; i < numbers.length; i += 2) {
        int currentStart = i;      // Mark start of current sequence
        
        // Extend sequence while next number is smaller
        while (i + 1 < numbers.length && numbers[i + 1] < numbers[i]) 
            i++;
        
        // Process sequence backwards to maintain alternation
        for (int currentIndex = i; currentIndex >= currentStart; currentIndex -= 2) 
            ans += numbers[currentIndex]; 
    }
    return ans;
}

Python Implementation:

def findScore(self, numbers: List[int]) -> int:
    ans = 0                        # Store final score
    i = 0                         # Start index
    
    # Process array in pairs
    while i < len(numbers):
        current_start = i         # Remember sequence start
        
        # Extend sequence while descending
        while i + 1 < len(numbers) and numbers[i + 1] < numbers[i]:
            i += 1
        
        # Take alternating numbers from sequence
        # Going backwards ensures correct alternation
        for j in range(i, current_start - 1, -2):
            ans += numbers[j]
        
        i = max(i + 1, current_start + 2)  # Move to next even position
    
    return ans

C++ Implementation:

long long findScore(vector& numbers) {
    long long ans = 0;            // Use long long for large numbers
    
    // Process even indices
    for (int i = 0; i < numbers.size(); i += 2) {
        int currentStart = i;     // Mark sequence start
        
        // Find end of descending sequence
        while (i + 1 < numbers.size() && 
               numbers[i + 1] < numbers[i]) {
            i++;
        }
        
        // Process sequence backwards
        // Take every other number
        for (int j = i; j >= currentStart; j -= 2) {
            ans += numbers[j];
        }
    }
    
    return ans;
}

Complexity:

Time Complexity: O(n), single pass through array
Space Complexity: O(1), constant extra space

Implementation Notes:

• **Edge Cases**:
  • Handle array bounds carefully
  • Consider overflow with large numbers
  • Work correctly for both odd and even lengths
• **Optimization**:
  • In-place processing without extra space
  • Single pass through array
  • Efficient sequence detection