LeetCode 1800 - Maximum Ascending Subarray Sum

LeetCode Problem 1800

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives an array of positive integers called nums. We must find the contiguous subarray that is strictly increasing and has the largest possible sum.

A subarray is contiguous, which means the elements must appear next to each other in the original array. We are not allowed to skip elements.

The phrase "strictly increasing" means every element in the subarray must be greater than the previous one. For example:

• [5, 10, 50] is valid because 5 < 10 < 50
• [10, 10, 20] is not valid because 10 is not strictly less than 10

The goal is to compute the maximum sum among all valid ascending subarrays.

For example, in:

[10,20,30,5,10,50]

There are two important ascending segments:

• [10,20,30] with sum 60
• [5,10,50] with sum 65

The correct answer is 65.

The constraints are small:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Since the array length is at most 100, even less efficient solutions would work. However, the problem is designed to encourage recognizing a simple linear scan solution.

A few important observations and edge cases:

• A single element is always a valid ascending subarray.
• If the entire array is strictly increasing, the answer is the sum of the whole array.
• If the array is strictly decreasing, the answer is simply the maximum individual element.
• Equal adjacent values break the ascending condition because the increase must be strict.
• Because all numbers are positive, extending an ascending subarray always increases its sum, which simplifies the logic.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible subarray.

For each starting index, we can extend the subarray one element at a time while checking whether it remains strictly increasing. If it does, we compute its sum and update the answer.

This works because it explicitly evaluates every valid ascending subarray, guaranteeing that the maximum sum will eventually be found.

However, this method repeatedly recomputes sums and repeatedly checks increasing conditions for overlapping ranges. Although the constraints are small enough for this to pass, it is inefficient compared to what is actually needed.

Optimal Approach

The key observation is that we only care about contiguous increasing runs.

As we scan the array from left to right:

• If the current number is greater than the previous one, we can extend the current ascending subarray.
• Otherwise, the ascending sequence breaks, so we must start a new subarray from the current element.

This means we never need nested loops. We can maintain:

• current_sum, the sum of the current ascending segment
• max_sum, the best answer seen so far

Each element is processed exactly once, giving a clean linear time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all possible ascending subarrays
Optimal	O(n)	O(1)	Single pass tracking current ascending segment

Algorithm Walkthrough

1. Initialize two variables:

• current_sum to the first element
• max_sum to the first element

We do this because a single element itself forms a valid ascending subarray. 2. Start iterating from index 1 to the end of the array. 3. For each element, compare it with the previous element:

• If nums[i] > nums[i - 1], the ascending sequence continues.
• Add nums[i] to current_sum.

4. Otherwise, the ascending sequence breaks:

• Reset current_sum to nums[i]
• This starts a new ascending subarray beginning at the current element.

5. After updating current_sum, compare it with max_sum:

• If current_sum is larger, update max_sum.

6. Continue until all elements are processed.
7. Return max_sum.

Why it works

The algorithm maintains the invariant that current_sum always represents the sum of the current strictly increasing contiguous segment ending at the current index.

Whenever the increasing condition fails, no valid ascending subarray can continue across that boundary, so resetting is correct.

Since every ascending segment is considered exactly once and max_sum stores the largest segment sum seen so far, the final answer is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        current_sum = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current_sum += nums[i]
            else:
                current_sum = nums[i]

            max_sum = max(max_sum, current_sum)

        return max_sum

The implementation starts by initializing both current_sum and max_sum with the first element. This works because at minimum, a single number is a valid ascending subarray.

The loop begins from index 1 because each element must be compared with its predecessor.

Inside the loop, the condition:

nums[i] > nums[i - 1]

checks whether the ascending sequence continues. If it does, we extend the current subarray by adding the current value.

If the condition fails, the ascending run has ended. Since the current value cannot belong to the previous ascending subarray, we reset current_sum to start a new segment.

After each update, we compare current_sum against max_sum to keep track of the best answer found so far.

Finally, the function returns max_sum.

Go Solution

func maxAscendingSum(nums []int) int {
    currentSum := nums[0]
    maxSum := nums[0]

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            currentSum += nums[i]
        } else {
            currentSum = nums[i]
        }

        if currentSum > maxSum {
            maxSum = currentSum
        }
    }

    return maxSum
}

The Go implementation follows the exact same logic as the Python version.

One small difference is that Go does not provide a built in max function for integers, so we use a simple if statement to update maxSum.

The constraints are very small, so integer overflow is not a concern. The maximum possible sum is only 100 * 100 = 10000, which easily fits within Go's int type.

The problem guarantees at least one element in the array, so accessing nums[0] is always safe.

Worked Examples

Example 1

Input:

nums = [10,20,30,5,10,50]

Index	Value	Comparison	current_sum	max_sum
0	10	Start	10	10
1	20	20 > 10	30	30
2	30	30 > 20	60	60
3	5	5 < 30	5	60
4	10	10 > 5	15	60
5	50	50 > 10	65	65

Final answer:

65

Example 2

Input:

nums = [10,20,30,40,50]

Index	Value	Comparison	current_sum	max_sum
0	10	Start	10	10
1	20	20 > 10	30	30
2	30	30 > 20	60	60
3	40	40 > 30	100	100
4	50	50 > 40	150	150

Final answer:

150

Example 3

Input:

nums = [12,17,15,13,10,11,12]

Index	Value	Comparison	current_sum	max_sum
0	12	Start	12	12
1	17	17 > 12	29	29
2	15	15 < 17	15	29
3	13	13 < 15	13	29
4	10	10 < 13	10	29
5	11	11 > 10	21	29
6	12	12 > 11	33	33

Final answer:

33

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan through the array. No nested loops or auxiliary data structures are required.

Because only current_sum and max_sum are stored, the extra memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        current_sum = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current_sum += nums[i]
            else:
                current_sum = nums[i]

            max_sum = max(max_sum, current_sum)

        return max_sum

solution = Solution()

assert solution.maxAscendingSum([10,20,30,5,10,50]) == 65  # provided example
assert solution.maxAscendingSum([10,20,30,40,50]) == 150  # entire array increasing
assert solution.maxAscendingSum([12,17,15,13,10,11,12]) == 33  # multiple resets
assert solution.maxAscendingSum([100]) == 100  # single element array
assert solution.maxAscendingSum([5,4,3,2,1]) == 5  # strictly decreasing
assert solution.maxAscendingSum([1,2,3,4]) == 10  # fully increasing
assert solution.maxAscendingSum([3,3,3]) == 3  # equal elements break sequence
assert solution.maxAscendingSum([1,5,2,3,4]) == 9  # best segment at the end
assert solution.maxAscendingSum([9,1,2,3]) == 9  # single large value beats later sequence
assert solution.maxAscendingSum([1,2,1,2,1,2]) == 3  # repeated short increasing runs

Test	Why
[10,20,30,5,10,50]	Validates normal mixed behavior
[10,20,30,40,50]	Tests fully increasing array
[12,17,15,13,10,11,12]	Tests multiple resets
[100]	Tests minimum array size
[5,4,3,2,1]	Tests strictly decreasing input
[1,2,3,4]	Tests one continuous ascending segment
[3,3,3]	Tests equal adjacent elements
[1,5,2,3,4]	Tests best subarray appearing later
[9,1,2,3]	Tests when single element is optimal
[1,2,1,2,1,2]	Tests repeated restarting behavior

Edge Cases

One important edge case is a single element array. Since a single number is itself a valid ascending subarray, the algorithm must correctly return that value immediately. Initializing both current_sum and max_sum with nums[0] ensures this works naturally without requiring special handling later.

Another important case is when the array is strictly decreasing. In this situation, every ascending subarray has length one. A buggy implementation might incorrectly accumulate values across decreasing boundaries. This implementation resets current_sum whenever the ascending condition fails, ensuring only valid segments are counted.

Equal adjacent values are also a subtle edge case. The problem requires strictly increasing order, not non decreasing order. That means sequences like [3,3] must break the current subarray. The condition:

nums[i] > nums[i - 1]

correctly enforces strict inequality.

A final important case is when the best ascending subarray appears near the end of the array. Some incorrect solutions only update the maximum when a sequence ends. This implementation updates max_sum during every iteration, so late optimal segments are handled correctly.