LeetCode 刷题系列 -- 1425. 带限制的子序列和

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。
示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。
示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/constrained-subsequence-sum
 

思路:

 定义子序列和，sums[i]  表示 以 nums[i] 结尾的限制子序列和的最大值.

  状态转移方程:

    sums[ i ] = max(sums[ i ], sums[ j ] + nums[ i ]);   //  i - k< = j < i

c++

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
 
        // 定义子序列和，sums[i]  表示 以 nums[i] 结尾的限制子序列和的最大值
        vector<int> sums(nums.size());
 
        // 初始化 base case
        for(int i=0;i<nums.size();i++) {
            sums[i] = nums[i];
        }
        int maxSum = nums[0];
 
        for(int i=1;i<nums.size();i++) {
            for(int j=i-1;j>=0 && i-j<=k;j--) {
                sums[i] = max(sums[i], nums[i] + sums[j]);
                maxSum = max(maxSum,sums[i]);
            }
        }
 
        return maxSum;
    }
};