Domain 1EasyCORE

Maximum Ascending Subarray Sum

The problem asks us to find the maximum possible sum of an ascending subarray within a given array of positive integers. An ascending subarray is defined as a contiguous sequence where each element is greater than the previous one. The input is an array of positive integers, and the output should be the sum of the ascending subarray with the highest sum. Edge cases include arrays with only one element, arrays that are entirely descending, and arrays where multiple ascending subarrays have the same maximum sum.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Two Pointers

1800. Maximum Ascending Subarray Sum

Model: qwen2.5-coder:14b
Topics: Two Pointers
FAANG asked: 0
Acceptance rate: 65.7%


Problem Breakdown

The problem asks us to find the maximum possible sum of an ascending subarray within a given array of positive integers. An ascending subarray is defined as a contiguous sequence where each element is greater than the previous one. The input is an array of positive integers, and the output should be the sum of the ascending subarray with the highest sum. Edge cases include arrays with only one element, arrays that are entirely descending, and arrays where multiple ascending subarrays have the same maximum sum.

Intuition

A brute-force approach would involve checking all possible subarrays to find the ascending ones and then calculating their sums. This approach is inefficient with a time complexity of O(n^2) because it requires nested loops to generate and check each subarray. The key insight is to use a single pass through the array while maintaining a running sum of the current ascending subarray. Whenever we encounter an element that breaks the ascending order, we compare the current sum with the maximum sum found so far and reset the running sum if necessary.

Approach

We will use a single-pass approach to solve this problem efficiently. We initialize variables current_sum and max_sum to keep track of the sum of the current ascending subarray and the maximum sum found so far, respectively.

  1. Iterate through the array starting from the second element.
  2. If the current element is greater than the previous one, add it to current_sum.
  3. If the current element is not greater than the previous one, compare current_sum with max_sum. Update max_sum if current_sum is larger, then reset current_sum to the value of the current element.
  4. After the loop, perform a final comparison between current_sum and max_sum to ensure the last subarray is considered.
  5. Return max_sum.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array with constant-time operations inside the loop.
  • Space Complexity: O(1). We use a fixed amount of extra space for variables regardless of the input size.

Solution

def maxAscendingSum(nums):
    if not nums:
        return 0
    
    current_sum = nums[0]
    max_sum = nums[0]
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            current_sum += nums[i]
        else:
            max_sum = max(max_sum, current_sum)
            current_sum = nums[i]
    
    # Final comparison to ensure the last subarray is considered
    max_sum = max(max_sum, current_sum)
    
    return max_sum

Edge Cases Handled

  • Single-element array: The algorithm correctly returns the single element as the maximum sum.
  • Entirely descending array: The algorithm will return the largest single element since no ascending subarray exists.
  • Multiple ascending subarrays with the same maximum sum: The algorithm will return the first encountered maximum sum.