Maximum Ascending Subarray Sum

Easy

#1646Time: O(n^2), where `n` is the length of the input array `nums`. The two nested loops result in a quadratic runtime in the worst-case scenario (e.g., a sorted array).Space: O(1), as it only uses a few variables to store sums and indices, regardless of the input size.1 company

Data structures

Array

Companies

tcs

Prompt

Given an array of positive integers nums, return the maximum possible sum of an strictly increasing subarray in nums.

A subarray is defined as a contiguous sequence of numbers in an array.

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 <= 100
1 <= nums[i] <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible contiguous subarray. For each potential starting point in the array, it extends the subarray as long as the elements are strictly increasing, calculates the sum, and updates the overall maximum sum found.

Algorithm

Initialize a variable maxSum to 0 to store the maximum sum found.
Iterate through the array with an outer loop using index i from 0 to n-1. This index i will be the starting point of a potential ascending subarray.
For each i, initialize currentSum = nums[i].
Start an inner loop with index j from i + 1 to n-1.
Inside the inner loop, check if nums[j] > nums[j-1].
- If it is, the subarray is still ascending. Add nums[j] to currentSum.
- If it's not, the ascending sequence is broken. Break the inner loop.
After the inner loop finishes (either by completion or by breaking), the currentSum holds the sum of the ascending subarray starting at i. Update maxSum = Math.max(maxSum, currentSum).
After the outer loop completes, maxSum will hold the result.

Walkthrough

The brute-force method iterates through all possible starting positions of a subarray. For each starting position i, it builds an ascending subarray by moving to the right (incrementing j). It keeps a currentSum for the subarray starting at i and extending to j. As long as nums[j] is greater than nums[j-1], the subarray is extended, and currentSum is updated. If the ascending property is violated, the extension stops for the current starting point i. The global maxSum is updated whenever a currentSum for a valid ascending subarray is calculated. This ensures all ascending subarrays are considered, and the one with the maximum sum is found.

1class Solution {2    public int maxAscendingSum(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }6        int maxSum = 0;7        for (int i = 0; i < nums.length; i++) {8            int currentSum = nums[i];9            for (int j = i + 1; j < nums.length; j++) {10                if (nums[j] > nums[j - 1]) {11                    currentSum += nums[j];12                } else {13                    break;14                }15            }16            maxSum = Math.max(maxSum, currentSum);17        }18        return maxSum;19    }20}

Complexity

Time

O(n^2), where `n` is the length of the input array `nums`. The two nested loops result in a quadratic runtime in the worst-case scenario (e.g., a sorted array).

Space

O(1), as it only uses a few variables to store sums and indices, regardless of the input size.

Trade-offs

Pros

Straightforward to conceptualize and implement.
Guaranteed to be correct as it checks all possibilities.

Cons

Inefficient for large inputs due to its quadratic time complexity.
Performs redundant computations by re-evaluating parts of subarrays.

An optimal single-pass approach that iterates through the array once. It maintains the sum of the current ascending subarray. When the ascending order is broken, it compares the current sum with the maximum sum found so far and then starts a new sum. This is a greedy approach that makes the locally optimal choice at each step.

Algorithm

Initialize maxSum and currentSum with the value of the first element, nums[0].
Iterate through the array from the second element (i = 1) to the end.
In each iteration, compare the current element nums[i] with the previous one nums[i-1].
If nums[i] > nums[i-1], the ascending sequence continues. Add nums[i] to currentSum.
If nums[i] <= nums[i-1], the ascending sequence is broken. Reset currentSum to the value of the current element nums[i], as this starts a new potential ascending subarray.
After updating currentSum in each step, compare it with maxSum and update maxSum if currentSum is larger: maxSum = Math.max(maxSum, currentSum).
After the loop finishes, return maxSum.

Walkthrough

This efficient method avoids nested loops by processing the array in a single pass. It uses a currentSum variable to track the sum of the ascending subarray being examined. It also uses a maxSum variable to keep track of the highest sum found so far. The algorithm starts by initializing both sums with the first element. Then, it iterates from the second element. If an element is greater than its predecessor, it's part of the current ascending subarray, so its value is added to currentSum. If it's less than or equal to its predecessor, the ascending streak is broken. At this point, the current ascending subarray ends, and a new one begins with the current element, so currentSum is reset to nums[i]. In every iteration, maxSum is updated to be the maximum of its current value and currentSum. This ensures that we always keep track of the largest sum seen.

1class Solution {2    public int maxAscendingSum(int[] nums) {3        if (nums == null || nums.length == 0) {4            return 0;5        }6        int maxSum = nums[0];7        int currentSum = nums[0];8        for (int i = 1; i < nums.length; i++) {9            if (nums[i] > nums[i - 1]) {10                currentSum += nums[i];11            } else {12                currentSum = nums[i];13            }14            maxSum = Math.max(maxSum, currentSum);15        }16        return maxSum;17    }18}

Complexity

Time

O(n), where `n` is the length of `nums`. The algorithm involves a single loop through the array.

Space

O(1), as it only uses a constant number of variables (`maxSum`, `currentSum`, `i`) irrespective of the input array size.

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Requires constant extra space.
Simple, elegant, and the optimal solution for this problem.

Cons

This approach is optimal, so there are no significant cons for this problem.

Solutions

Solution

1class Solution {2public3  int maxAscendingSum(int[] nums) {4    int ans = 0, t = 0;5    for (int i = 0; i < nums.length; ++i) {6      if (i == 0 || nums[i] > nums[i - 1]) {7        t += nums[i];8        ans = Math.max(ans, t);9      } else {10        t = nums[i];11      }12    }13    return ans;14  }15}

1class Solution {2public:3  int maxAscendingSum(vector<int> &nums) {4    int ans = 0, t = 0;5    for (int i = 0; i < nums.size(); ++i) {6      if (i == 0 || nums[i] > nums[i - 1]) {7        t += nums[i];8        ans = max(ans, t);9      } else {10        t = nums[i];11      }12    }13    return ans;14  }15};

1class Solution:2    def maxAscendingSum(self, nums: List[int]) -> int: ans = t = 0 for i, v in enumerate(nums): if i == 0 or v > nums[i - 1]: t += v ans = max(ans, t) else: t = v return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem