{x}
blog image

Maximum Ascending Subarray Sum

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

Solution Explanation: Maximum Ascending Subarray Sum

The problem asks us to find the maximum sum of a contiguous subarray within a given array nums where the subarray elements are strictly increasing (ascending).

Approach: Single Pass Iteration

The most efficient approach involves a single pass through the input array. We maintain two variables:

  1. current_sum: This variable tracks the sum of the current ascending subarray.
  2. max_sum: This variable stores the maximum sum encountered so far.

The algorithm iterates through the array. If the current element is greater than the previous element, it means the ascending subarray continues. We add the current element to current_sum. If the current element is not greater than the previous element, it signifies the end of the current ascending subarray. In this case, we update max_sum with the maximum of max_sum and current_sum, and then reset current_sum to the current element, starting a new ascending subarray.

After the loop completes, we compare max_sum and current_sum one last time to account for the possibility that the last subarray is the largest. The final value of max_sum represents the maximum sum of an ascending subarray.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space Complexity: O(1). We use only a few constant extra variables.

Code Implementation (Python)

def maxAscendingSum(nums):
    max_sum = 0  # Initialize maximum sum
    current_sum = 0  # Initialize current subarray sum
    
    for i in range(len(nums)):
        if i == 0 or nums[i] > nums[i-1]:  # Check if ascending condition is met
            current_sum += nums[i]
        else:
            max_sum = max(max_sum, current_sum)  # Update max_sum if necessary
            current_sum = nums[i]  # Start a new subarray
            
    max_sum = max(max_sum, current_sum)  # Check the last subarray
    return max_sum

Code Implementation (Other Languages):

The approach remains the same across different programming languages. The only changes are in syntax and function/method naming conventions. Refer to the solution provided in the original response for examples in Java, C++, Go, TypeScript, Rust and C. The core logic of maintaining current_sum and max_sum remains consistent.