Maximum Ascending Subarray Sum - Solution & Explanation
Problem Statement
Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.
A subarray is defined as a contiguous sequence of numbers in an array.
A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.
Example 1:
Input: nums = [10,20,30,5,10,50] Output: 65 Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.
Example 2:
Input: nums = [10,20,30,40,50] Output: 150 Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.
Example 3:
Input: nums = [12,17,15,13,10,11,12] Output: 33 Explanation: [10,11,12] is the ascending subarray with the maximum sum of 33.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Approach Overview
Problem Overview: You are given an integer array and need to compute the maximum possible sum of a contiguous subarray where each element is strictly greater than the previous one. The subarray must remain strictly ascending from left to right, and the goal is to track the highest sum among all such segments.
This problem falls under common array traversal patterns. The key challenge is recognizing when an ascending streak continues and when it breaks so you can reset the running total.
Approach 1: Single Pass with Current Sum Tracker (O(n) time, O(1) space)
Scan the array once while maintaining two variables: currentSum for the sum of the current ascending segment and maxSum for the best result seen so far. Start with the first element as the current sum. While iterating, check if nums[i] > nums[i-1]. If true, the ascending order continues, so add the element to currentSum. If not, the ascending streak breaks and you reset currentSum to the current element. After each step, update maxSum = max(maxSum, currentSum). This works because every ascending segment is processed exactly once, and each element contributes to at most one running sum.
The insight is that an ascending subarray cannot extend across a non-increasing boundary. Instead of checking every possible subarray, you treat each increasing run as a single candidate segment. The algorithm performs a single linear pass through the array, giving O(n) time complexity and constant O(1) space.
Approach 2: Divide and Conquer Strategy (O(n log n) time, O(log n) space)
This approach recursively splits the array into two halves, similar to classic divide-and-conquer patterns. For each segment, compute three values: the best ascending subarray entirely in the left half, the best entirely in the right half, and a potential ascending subarray that crosses the midpoint. The crossing case is valid only if the boundary elements maintain the strictly increasing condition.
During the merge step, you combine results from both halves while checking whether the rightmost value of the left segment is smaller than the leftmost value of the right segment. If so, the ascending sequence can extend across the midpoint, and you compute the combined sum. Recursion depth contributes O(log n) stack space, and each level processes O(n) work, leading to O(n log n) total time.
Recommended for interviews: The single-pass running sum approach is what interviewers expect. It demonstrates strong understanding of array traversal and state tracking while achieving optimal O(n) time and O(1) space. The divide-and-conquer version is academically interesting and shows familiarity with recursive decomposition, but it introduces unnecessary overhead for this problem.
Approach 1: Using a Single Pass with Current Sum Tracker
This approach uses a single pass over the array while maintaining a current sum of an ascending subarray. As we iterate over the array, we check if the current number is greater than the previous one to have an ascending subarray.
If the current number is greater, add it to the current sum; otherwise, check if the current sum is greater than the maximum sum found so far and reset the current sum to the current number.
Finally, ensure to compare the last current sum with the maximum sum after the loop to cover the case where the array ends with an ascending subarray.
The solution initializes max_sum and current_sum with the first element. As it iterates, it adds the current element to current_sum if it's greater than the previous one; otherwise, it resets current_sum. It updates max_sum accordingly.
Code
Python
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once.
Space Complexity: O(1), as we only use a constant amount of extra space for variables.
Approach 2: Divide and Conquer Strategy
This approach utilizes a divide and conquer technique. The concept involves dividing the array into two halves, recursively finding the maximum ascending subarray sum in each half, and considering the possibility of maximum ascending subarray crossing the midpoint.
We combine these results to derive the solution.
The C++ solution uses a helper function to recursively divide the array and find the maximum sum across three potential sections (left half, right half, and crossing subarray). The function maxCrossingSum calculates the maximum sum of ascending elements crossing the middle of the divided part.
Complexity
Time Complexity: O(n log n), due to the divide and conquer division similar to merge sort.
Space Complexity: O(log n), due to the recursion stack used in the divide and conquer approach.
Approach 3: Direct Simulation
We use a variable t to record the current sum of the ascending subarray, and a variable ans to record the maximum sum of the ascending subarray.
Traverse the array nums:
If the current element is the first element of the array, or the current element is greater than the previous one, then add the current element to the sum of the current ascending subarray, i.e., t = t + nums[i], and update the maximum sum of the ascending subarray ans = max(ans, t). Otherwise, the current element does not satisfy the condition of the ascending subarray, so reset the sum t of the current ascending subarray to the current element, i.e., t = nums[i].
After the traversal, return the maximum sum of the ascending subarray ans.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Single Pass with Current Sum Tracker | Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once. |
| Divide and Conquer Strategy | Time Complexity: O(n log n), due to the divide and conquer division similar to merge sort. |
| Direct Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass with Current Sum Tracker | O(n) | O(1) | Best general solution. Linear scan with constant memory, ideal for interviews and production. |
| Divide and Conquer Strategy | O(n log n) | O(log n) | Useful for practicing recursive array decomposition or divide-and-conquer patterns. |
Video Solution
Maximum Ascending Subarray Sum - Leetcode 1800 - Python • NeetCodeIO • 5,652 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Ascending Subarray Sum easy or hard?
Maximum Ascending Subarray Sum Python/Java solution
How to solve Maximum Ascending Subarray Sum in O(n)?
What is the best approach for Maximum Ascending Subarray Sum?
Is Maximum Ascending Subarray Sum asked at Google/Amazon/Meta?
What data structure is used in Maximum Ascending Subarray Sum?
What is the time complexity of Maximum Ascending Subarray Sum?
Ready to solve this problem?
Practice Maximum Ascending Subarray Sum with our built-in code editor and test cases.
Practice on FleetCode