Problem

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 < rnumsi < numsi+1. Note that a subarray of size 1 is ascending.

Examples

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

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

The naive approach to solving this problem involves checking all possible subarrays to identify those that are ascending and calculating their sums. Here’s how the naive approach works:

  • We initialize maxSum to the smallest possible integer value.
  • Loop through each index i from 0 to n-1 as the starting point of the subarray.
  • For each starting point, initialize currSum to 0 and extend the subarray to the right (from i to n-1). Add each element to currSum.
  • If the next element is not greater than the current one, break the inner loop.
  • Track the maximum sum encountered during the process.

Code

Java
class Solution {
    public int maxAscendingSum(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currSum = 0;
            for (int j = i; j < n; j++) {
                currSum += nums[j];
                maxSum = Math.max(maxSum, currSum);
                if (j < n - 1 && nums[j] >= nums[j+1]) {
                    break;
                } 
            }
        }
        return maxSum;
    }
}
Python
class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        max_sum = float('-inf')
        n = len(nums)
        for i in range(n):
            curr_sum = 0
            for j in range(i, n):
                curr_sum += nums[j]
                max_sum = max(max_sum, curr_sum)
                if j < n - 1 and nums[j] >= nums[j + 1]:
                    break
        return max_sum

Complexity

  • ⏰ Time complexity: O(n^2), because of nested loop.
  • 🧺 Space complexity: O(1), because we are only using a fixed amount of extra space for the variable max_sum.

Method 2 - Kadane like logic

The problem requires finding the maximum possible sum of an ascending subarray. To achieve this, we can iterate through the array while maintaining the sum of the current ascending subarray and updating the maximum sum whenever a higher sum is found. If a number breaks the ascending property, we reset the current sum to start a new potential ascending subarray.

Approach

  1. Initialize ans to store the maximum sum found so far, and current_sum to maintain the sum of the current ascending subarray.
  2. Iterate through the array. For each element:
    • If it is the start of the array or maintains the ascending property with respect to the previous element, add it to current_sum.
    • Otherwise, update ans if current_sum is greater than ans, and reset current_sum to the current element.
  3. After the loop, make sure to update ans with current_sum one last time in case the longest ascending subarray is at the end of the array.
  4. Return ans, which holds the maximum sum of an ascending subarray.

Code

Java
class Solution {
    public int maxAscendingSum(int[] nums) {
        int ans = nums[0], currSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] < nums[i]) {
                currSum += nums[i];
            } else {
                currSum = nums[i];
            }
            ans = Math.max(ans, currSum);
        }
        
        return ans;
    }
}
Python
class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        ans = nums[0]
        curr_sum = nums[0]
        
        for i in range(1, len(nums)):
            if nums[i - 1] < nums[i]:
                curr_sum += nums[i]
            else:
                curr_sum = nums[i]
            ans = max(ans, curr_sum)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), because we iterate through the array exactly once.
  • 🧺 Space complexity: O(1), because we use only a fixed amount of extra space regardless of the input size.