题解 | #不相邻最大子序列和#

打家劫舍题

设dp[i]为以i为结尾的目标值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    long long subsequence(int n, vector<int>& nums) {
        // write code here
        if(n == 1) return max(0, nums[0]);
        if(n == 2) return max({0, nums[0], nums[1]});
        if(n == 3) return max({0, nums[0], nums[1], nums[2], nums[0] + nums[2]});
        long long dp[n];
        memset(dp, 0, sizeof(dp));
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = max(nums[2], nums[2] + nums[0]);
        long long ans = max({(long long)0, dp[0], dp[1], dp[2]});
        for(int i = 3; i < n; i ++){
            dp[i] = max({(long long)nums[i], dp[i - 2] + nums[i], dp[i - 3] + nums[i]});
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

设dp[i]表示前i个元素的目标值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    long long subsequence(int n, vector<int>& nums) {
        // write code here
        if(n == 1) return max(0, nums[0]);
        if(n == 2) return max({0, nums[0], nums[1]});
        long long dp[n];
        memset(dp, 0, sizeof(dp));
        dp[0] = max(0, nums[0]);
        dp[1] = max({0, nums[0], nums[1]});
        long long ans = max({(long long)0, dp[0], dp[1]});
        for(int i = 2; i < n; i ++){
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};