Problem Description

You are given an array of positive integers nums. Your task is to find the maximum possible sum of a strictly increasing subarray within nums.

A subarray is a contiguous sequence of elements from the array. A strictly increasing subarray means each element must be greater than the previous element in that subarray.

For example, if nums = [10, 20, 30, 5, 10, 50]:

• [10, 20, 30] is a strictly increasing subarray with sum 60
• [5, 10, 50] is a strictly increasing subarray with sum 65
• [30, 5] is NOT strictly increasing because 5 < 30

The algorithm works by traversing through the array and maintaining a running sum t of the current strictly increasing subarray. When we encounter an element that is greater than the previous one, we add it to our current sum. When we encounter an element that is not greater than the previous one, we start a new subarray from that element. Throughout this process, we keep track of the maximum sum seen so far in the variable ans.

The key steps are:

1. If the current element is the first element OR it's greater than the previous element, add it to the current sum t and update the maximum ans
2. Otherwise, reset the current sum t to just the current element (starting a new subarray)
3. Return the maximum sum found

Intuition

When looking at this problem, we need to find the maximum sum among all possible strictly increasing subarrays. The key insight is that we can solve this in a single pass through the array.

Think about it this way: as we traverse the array, at each position we have two possibilities:

1. The current element is greater than the previous one - we can extend our current increasing subarray
2. The current element is not greater than the previous one - we must start a new increasing subarray

This naturally leads to a greedy approach. We want to keep building our current increasing subarray as long as possible (since we're adding positive numbers, a longer valid subarray means a larger sum). But the moment we encounter a number that breaks the strictly increasing property, we have no choice but to start fresh from that number.

Why does this work? Because subarrays must be contiguous, we can't skip elements. So when we hit a number that's not greater than the previous one, any strictly increasing subarray containing this number cannot include the previous elements - it must start from this position.

The beauty of this approach is that we only need to track two things:

• t: the sum of the current strictly increasing subarray we're building
• ans: the maximum sum we've seen so far

As we build each strictly increasing subarray, we continuously update our answer with the maximum sum seen. This ensures we don't miss any potential maximum, and by the end of our traversal, we'll have checked all possible strictly increasing subarrays.

The time complexity is O(n) since we visit each element exactly once, and the space complexity is O(1) as we only use two variables regardless of input size.

Solution Approach

The implementation uses a direct simulation approach with two variables to track the state as we traverse the array:

1. Initialize variables:

   • ans = 0: Tracks the maximum sum of strictly increasing subarray found so far
   • t = 0: Tracks the current sum of the strictly increasing subarray being built

2. Traverse the array using enumeration: We iterate through the array using enumerate(nums) to get both the index i and value v at each position.

3. Check the strictly increasing condition: For each element, we check if it can extend the current strictly increasing subarray:

   • if i == 0 or v > nums[i - 1]:
     • If it's the first element (i == 0), we always start a new subarray
     • If the current value v is greater than the previous element nums[i - 1], we can extend the current subarray

4. Handle the two cases:

   Case 1: Element extends the current increasing subarray

   • Add the current element to the running sum: t += v
   • Update the maximum sum if current sum is larger: ans = max(ans, t)

   Case 2: Element breaks the increasing pattern

   • Reset the current sum to just this element: t = v
   • This starts a new strictly increasing subarray from the current position

5. Return the result: After traversing the entire array, ans contains the maximum sum of all strictly increasing subarrays encountered.

The algorithm processes each element exactly once, making decisions based only on the current and previous elements. This greedy approach ensures we capture the maximum sum by always extending subarrays when possible and resetting when necessary.

Example walkthrough with nums = [10, 20, 30, 5, 10, 50]:

• i=0, v=10: First element, t=10, ans=10
• i=1, v=20: 20 > 10, extend: t=30, ans=30
• i=2, v=30: 30 > 20, extend: t=60, ans=60
• i=3, v=5: 5 < 30, reset: t=5, ans=60
• i=4, v=10: 10 > 5, extend: t=15, ans=60
• i=5, v=50: 50 > 10, extend: t=65, ans=65
• Return 65

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [3, 1, 4, 7, 2, 5]

We'll track two variables:

• t: current strictly increasing subarray sum
• ans: maximum sum found so far

Step-by-step execution:

Position 0: value = 3

• First element, so we start a new subarray
• t = 3 (start new subarray with value 3)
• ans = max(0, 3) = 3
• Current increasing subarray: [3]

Position 1: value = 1

• Check: Is 1 > 3? No
• Cannot extend current subarray, must start new one
• t = 1 (reset to just this element)
• ans = max(3, 1) = 3 (keep previous maximum)
• Current increasing subarray: [1]

Position 2: value = 4

• Check: Is 4 > 1? Yes
• Can extend current subarray
• t = 1 + 4 = 5 (add to current sum)
• ans = max(3, 5) = 5
• Current increasing subarray: [1, 4]

Position 3: value = 7

• Check: Is 7 > 4? Yes
• Can extend current subarray
• t = 5 + 7 = 12 (add to current sum)
• ans = max(5, 12) = 12
• Current increasing subarray: [1, 4, 7]

Position 4: value = 2

• Check: Is 2 > 7? No
• Cannot extend current subarray, must start new one
• t = 2 (reset to just this element)
• ans = 12 (keep previous maximum)
• Current increasing subarray: [2]

Position 5: value = 5

• Check: Is 5 > 2? Yes
• Can extend current subarray
• t = 2 + 5 = 7 (add to current sum)
• ans = max(12, 7) = 12
• Current increasing subarray: [2, 5]

Final Result: 12

The maximum sum comes from the strictly increasing subarray [1, 4, 7] with sum = 12.

This example demonstrates how the algorithm:

1. Extends the current subarray when possible (when elements are strictly increasing)
2. Resets and starts a new subarray when the increasing pattern breaks
3. Continuously tracks the maximum sum throughout the traversal

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once using a single for loop with enumerate, performing constant-time operations (comparisons, additions, and max operations) for each element.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size - it maintains just two variables: ans to track the maximum sum found and t to track the current ascending subarray sum. The loop variables i and v also use constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Update Maximum When Breaking Sequence

The Problem: A common mistake is only updating the maximum sum (max_sum) when extending an ascending subarray, but forgetting to consider single-element subarrays or the first element of a new subarray when the sequence breaks.

Incorrect Implementation:

def maxAscendingSum(self, nums: List[int]) -> int:
    max_sum = 0
    current_sum = 0
  
    for index, value in enumerate(nums):
        if index == 0 or value > nums[index - 1]:
            current_sum += value
            max_sum = max(max_sum, current_sum)  # Only updating here
        else:
            current_sum = value  # Forgot to update max_sum here!
  
    return max_sum

Why It Fails: Consider nums = [12, 17, 15, 13, 10, 11, 12]:

• The subarray [12, 17] gives sum 29
• When we hit 15, we reset to current_sum = 15 but don't check if 15 > max_sum
• If all subsequent elements are decreasing except small increases, we might miss single-element maximums

Correct Solution:

def maxAscendingSum(self, nums: List[int]) -> int:
    max_sum = 0
    current_sum = 0
  
    for index, value in enumerate(nums):
        if index == 0 or value > nums[index - 1]:
            current_sum += value
        else:
            current_sum = value
        max_sum = max(max_sum, current_sum)  # Always update after modifying current_sum
  
    return max_sum

Pitfall 2: Using Wrong Comparison Operator

The Problem: Using >= instead of > for the strictly increasing condition, which would include equal elements in the "ascending" subarray.

Incorrect Implementation:

if index == 0 or value >= nums[index - 1]:  # Wrong: >= instead of >
    current_sum += value

Why It Fails: For nums = [1, 2, 2, 3]:

• Using >= would give [1, 2, 2, 3] with sum 8
• But [2, 2] is NOT strictly increasing (elements must be strictly greater)
• The correct answer should be max of [1, 2] (sum 3) and [2, 3] (sum 5), which is 5

Pitfall 3: Initializing current_sum Incorrectly

The Problem: Initializing current_sum to the first element instead of 0, leading to double-counting the first element.

Incorrect Implementation:

def maxAscendingSum(self, nums: List[int]) -> int:
    max_sum = nums[0]  
    current_sum = nums[0]  # Wrong initialization
  
    for index, value in enumerate(nums):
        if index == 0 or value > nums[index - 1]:
            current_sum += value  # First element gets added again!
        else:
            current_sum = value
        max_sum = max(max_sum, current_sum)
  
    return max_sum

Why It Fails: For nums = [100, 10, 1]:

• Initial: current_sum = 100
• At index 0: current_sum += 100 → current_sum = 200 (incorrect!)
• The correct maximum should be 100, not 200