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 < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.
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 <= 1001 <= nums[i] <= 100This approach uses a single pass over the array while maintaining a current sum of an ascending subarray. As we iterate over the array, we check if the current number is greater than the previous one to have an ascending subarray.
If the current number is greater, add it to the current sum; otherwise, check if the current sum is greater than the maximum sum found so far and reset the current sum to the current number.
Finally, ensure to compare the last current sum with the maximum sum after the loop to cover the case where the array ends with an ascending subarray.
The solution initializes max_sum and current_sum with the first element. As it iterates, it adds the current element to current_sum if it's greater than the previous one; otherwise, it resets current_sum. It updates max_sum accordingly.
JavaScript
Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once.
Space Complexity: O(1), as we only use a constant amount of extra space for variables.
This approach utilizes a divide and conquer technique. The concept involves dividing the array into two halves, recursively finding the maximum ascending subarray sum in each half, and considering the possibility of maximum ascending subarray crossing the midpoint.
We combine these results to derive the solution.
The C++ solution uses a helper function to recursively divide the array and find the maximum sum across three potential sections (left half, right half, and crossing subarray). The function maxCrossingSum calculates the maximum sum of ascending elements crossing the middle of the divided part.
Java
Time Complexity: O(n log n), due to the divide and conquer division similar to merge sort.
Space Complexity: O(log n), due to the recursion stack used in the divide and conquer approach.
| Approach | Complexity |
|---|---|
| Using a Single Pass with Current Sum Tracker | Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once. |
| Divide and Conquer Strategy | Time Complexity: O(n log n), due to the divide and conquer division similar to merge sort. |
Maximum Ascending Subarray Sum - Leetcode 1800 - Python • NeetCodeIO • 4,560 views views
Watch 9 more video solutions →Practice Maximum Ascending Subarray Sum with our built-in code editor and test cases.
Practice on FleetCode