【LeetCode】1800. 最大升序子数组和

发表于 分类于 Valine：
本文字数： 87 阅读时长 ≈ 1 分钟

第233场周赛 1800. 最大升序子数组和

思路

  1. 动态规划
  2. 前缀和
  3. 滑动窗口

代码

前缀和、动态规划
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(nums);
        for(int i=1;i<n;i++)
        {
            if(nums[i]>nums[i-1]) ans[i]+=ans[i-1];
        }
        return *max_element(ans.begin(),ans.end());
    }
};
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int n = nums.size(), l = 0, r = 1, ans = INT_MIN;
        while(r < n){
            if(nums[r] > nums[r - 1]){// 单调递增
                r++;
                continue;
            }
            int sum = accumulate(nums.begin() + l, nums.begin() + r, 0); // 出现拐点就计算和
            ans = max(ans, sum);
            l = r;
            r++;
        }
        int sum = accumulate(nums.begin() + l, nums.end(), 0); // 计算和
        
        ans = max(ans, sum);
        return ans;
    }
};