Maximum Ascending Subarray Sum

EASY

Description

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

Checkout 2 different approaches to solve Maximum Ascending Subarray Sum. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as it only uses a few variables to store sums and indices, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Ascending Subarray Sum. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Ascending Subarray Sum

Data Structures:

Array

Companies:

tcs |