Scale Engineer

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.

class Solution {    public int maxAscendingSum(int[] nums) {        if (nums == null || nums.length == 0) {            return 0;        }        int maxSum = 0;        for (int i = 0; i < nums.length; i++) {            int currentSum = nums[i];            for (int j = i + 1; j < nums.length; j++) {                if (nums[j] > nums[j - 1]) {                    currentSum += nums[j];                } else {                    break;                }            }            maxSum = Math.max(maxSum, currentSum);        }        return maxSum;    }}

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.

Solutions

class Solution {public  int maxAscendingSum(int[] nums) {    int ans = 0, t = 0;    for (int i = 0; i < nums.length; ++i) {      if (i == 0 || nums[i] > nums[i - 1]) {        t += nums[i];        ans = Math.max(ans, t);      } else {        t = nums[i];      }    }    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 →

Next problem