5709. 最大升序子数组和

算法

暴力枚举 $O(n^2)$

• 枚举区间起点 i，计算区间内从 i 开始最长的上升子数组的终点 j，并求和
• 用最大的和更新答案

C++ 代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    int maxAscendingSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int sum = nums[i];
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > nums[j - 1]) {
                    sum += nums[j];
                } else {
                    break;
                }
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};