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.
- Iterate through the array starting from the second element.
- If the current element is greater than the previous one, add it to
current_sum. - If the current element is not greater than the previous one, compare
current_sumwithmax_sum. Updatemax_sumifcurrent_sumis larger, then resetcurrent_sumto the value of the current element. - After the loop, perform a final comparison between
current_sumandmax_sumto ensure the last subarray is considered. - 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.