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.
Example 4:
Input: nums = [100,10,1] Output: 100
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
Solution: Running sum with resetting
Time complexity: O(n)
Space complexity: O(1)
Track the running sum and reset it to zero if nums[i] <= nums[i – 1]
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int maxAscendingSum(vector<int>& nums) { int ans = 0; for (int i = 0, s = 0; i < nums.size(); ++i) { if (i && nums[i] <= nums[i - 1]) s = 0; ans = max(ans, s += nums[i]); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment