动态规划

1 最大子序和

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

链接：https://leetcode-cn.com/problems/maximum-subarray/

思路

1. 状态：$dp[i]$ 代表以$nums[i]$结尾的最大和
2. 状态转移方程：$dp[i] = max(dp[i-1]+nums[i], nums[i])$
3. 答案：$max(dp[0...n-1])$

• 时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$，可用滚动数组优化到$O(1)$。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int pre = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i++) {
            pre = max(nums[i], pre + nums[i]);
            ans = max(ans, pre);
        }
        return ans;
    }
};

2 最长上升子序列

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/

思路

1. 状态：$dp[i]$ 代表以$nums[i]$结尾的最长严格递增子序列的长度
2. 状态转移方程：$dp[i] = max(dp[j]+1,dp[i])$，$j<i$且$nums[i]>nums[j]$
3. 答案：max(dp[0…n-1])

• 时间复杂度： $O(n^2)$
• 空间复杂度： $O(n)$

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp, dp + n);
    }
};

3