Maximum Ascending Subarray Sum
Problem
Return the maximum sum of any strictly ascending contiguous subarray of nums.
nums = [10,20,30,5,10,50]65def max_ascending_sum(nums):
cur = best = nums[0]
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
cur += nums[i]
else:
cur = nums[i]
if cur > best: best = cur
return bestfunction maxAscendingSum(nums) {
let cur = nums[0], best = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = nums[i] > nums[i-1] ? cur + nums[i] : nums[i];
if (cur > best) best = cur;
}
return best;
}class Solution {
public int maxAscendingSum(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = nums[i] > nums[i-1] ? cur + nums[i] : nums[i];
best = Math.max(best, cur);
}
return best;
}
}int maxAscendingSum(vector<int>& nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
cur = nums[i] > nums[i-1] ? cur + nums[i] : nums[i];
best = max(best, cur);
}
return best;
}Explanation
We want the biggest sum of a run of numbers that keeps strictly going up. The simple idea: walk through the list once, keep adding to a running total as long as each number is bigger than the one before it, and remember the best total we ever reach.
The variable cur is the sum of the current ascending run. When nums[i] > nums[i-1], the run continues, so we do cur += nums[i]. Otherwise the run is broken, so we reset cur to just nums[i] and start fresh.
After each step we update best with max(best, cur), so the answer is the largest run sum we have seen.
Example: [10,20,30,5,10,50]. The run 10,20,30 builds cur up to 60. Then 5 drops, so we reset to 5, and 5,10,50 climbs to 65.
That final run beats everything, so best = 65. Because we only pass through the array once, this is very fast.