53. 最大子数组和
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
思路分析
这道题之前我们曾使用贪心方法解决过一次.这次我们使用动态规划进行解决.
动规五部曲
确定dp数组以及下标的含义
dp[i]:下标i之前(包括i)的最大连续子序列和为dp[i]
确定递推公式
dp[i]只有两个方向推出来
dp[i-1] + nums[i],即:nums[i]加入当前连续子序列和
nums[i],即:当nums[i]从头计算当前连续子序列和
一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
dp数组如何初始化
dp[i]依赖于dp[i-1]的状态,dp[0]就是递推公式的基础.
根据dp[0]的定义,很明显dp[0] = nums[0].
确定遍历顺序
根据递推公式,可以看出需要从前往后遍历
举例推导dp数组
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。所以需要在遍历过程中 及时更新结果集result.
参考代码
贪心法
//贪心法 int maxSubArray(vector<int>& nums) { int count = 0; int result = INT_MIN; for(int i = 0; i < nums.size(); i++) { count += nums[i]; result = count > result ? count : result; if(count < 0) { //如果count变成了负数,则从0重新开始.因为负数加任何数答案都会变小. count = 0; } } return result; }
动态规划法
//动态规划 int maxSubArray(vector<int>& nums) { vector<int> dp(nums.size(),0) ;//dp定义 dp[0] = nums[0] ;//dp初始化 int result = nums[0];//记录结果 //进行递推 for(int i = 1; i < nums.size(); i++) { dp[i] = max(dp[i-1]+nums[i],nums[i]);//dp[i] = max(使用当前数,从当前数重头开始) if(dp[i] > result) { result = dp[i]; } } return result; }
392. 判断子序列
题目描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
思路分析
这道题可以使用双指针的思路解决,很方便也易于理解,时间复杂度O ( n ) O(n)O(n)
我们接下来试一下动态规划,**动规五部曲**走起
确定dp数组以及下标的含义
dp[i] [j]表示:以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t,相同子序列长度为dp[i] [j]
确定递推公式
考虑两种情况:
if(s[i-1] == t[j-1])
t中找到了一个字符在s中也出现了, dp[i][j] = dp[i-1][j-1] +1
if(s[i-1] != t[j-1])
相当于t要删除元素,继续往后匹配, 删除后就是要比较 s[i-1]与t[j-2]的比较结果了,即:dp[i][j] = dp[i][j-1]
dp数组如何初始化
从递推公式可有看出dp[i] [j]都是依赖于dp[i-1] [j-1]和dp[i] [j-1],所以dp[0] [0]和dp[i] [0]一定是要初始化的.
这里大家已经可以发现，在定义dp[i] [j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i] [j]。
因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：
如果要是定义的dp[i] [j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。
dp[i] [0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0. dp[0] [j]同理。
我们可以定义时直接进行初始化,代码如下：
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
确定遍历顺序
同理从递推公式可以看出dp[i] [j]都是依赖于dp[i - 1] [j - 1] 和 dp[i] [j - 1]，那么遍历顺序也应该是从上到下，从左到右
如图所示：
举例推导dp数组
以示例一为例，输入：s = “abc”, t = “ahbgdc”，dp状态转移图如下：
双指针法
//双指针法 bool isSubsequence(string s, string t) { if(s.size()>t.size()) { return false; } int point1 = 0; for(int i = 0; i < t.size(); i++) { if(point1==s.size()) { break; } if(s[point1]==t[i]) { point1++; } } if(point1==s.size()) {//这里还是要判断一下,因为可能上面循环中,for循环结束时,s也刚好走完. return true; } return false; }
动态规划法
//动态规划 bool isSubsequence(string s, string t) { vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0)) ;//dp定义及初始化 //递推dp for(int i = 1; i <= s.size(); i++) { for(int j = 1;j <= t.size(); j++){ if(s[i] == t[j]){ dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = dp[i][j-1];//t中删除j-1的元素 相当于求s[0,i-1] ,t[0,j-2]的最大子序列长度. } } } return dp[s.size()][t.size()] == s.size(); }
