这次写两道有些类似的题目的分析。
1 题目
53. Maximum Subarray (Easy)
点击打开链接
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.
152. Maximum Product Subarray (Medium) 点击打开链接 Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
2 分析和代码
（1）求最大子序列和
方法一：遍历一遍array，用一个变量保存当前位置的最大和（局部），再筛选出全局最大和。该方法叫做Kadane算法，时间复杂度为O(n), 空间复杂度为O(1)
使用该方法也可以比较容易得到该子序列的开始和结束的位置。
代码如下：
int Max(int a, int b) { return a > b ? a : b; } class Solution { public: int maxSubArray(vector<int>& nums) { //maxSumLocal局部的最大和，maxSum记录全局最大和 int maxSumLocal = nums[0], maxSum = nums[0]; if(nums.size() == 1) return nums[0]; for(int i = 1; i < nums.size(); i++) { maxSumLocal = Max(maxSumLocal + nums[i], nums[i]); maxSum = Max(maxSumLocal, maxSum); } return maxSum; } };
方法二：将该问题看成一个动态规划问题
Base case： 建立一个与原数列A长度相同的数列dp，dp中的每一个值dp[i]表示以位置i为终点的子数列的最大和。
Induction case： 如果dp[i-1]>0,那么dp[i]=dp[i-1]+A[i]；否则dp[i]=A[i]。dp中的最大值就是最大连续子数列之和。
该方法的时间复杂度和空间复杂度都为O（n）
class Solution { public: int maxSubArray(vector<int>& nums) { vector<int>& dp = nums; int maxSum = nums[0]; if(nums.size() == 1) return nums[0]; for(int i = 1; i < nums.size(); i++) { if(dp[i - 1] >= 0 ) dp[i] = dp[i - 1] + nums[i]; else dp[i] = nums[i]; if(dp[i] > maxSum) maxSum = dp[i]; } return maxSum; } };
附上该问题的维基百科链接：点击打开链接
（2）最大子序列乘积
最大子序列乘积和最大子序列和的不同地方在于，在乘法里，最小的负数*负数也可以产生最大的乘积，因此参考最大子序列和的方法一，考虑增加一个变量存储局部的最小值。代码如下：
int Max(int a, int b) { return a > b ? a : b; } int Min(int a, int b) { return a < b ? a : b; } class Solution { public: int maxProduct(vector<int>& nums) { //需要同时记录局部最大值和局部最小值，因为乘法的负数*负数也可以产生最大的乘积 int maxLocal = nums[0], minLocal = nums[0]; int maxPro = nums[0]; if(nums.size() == 1) return nums[0]; for(int i = 1; i < nums.size(); i++) { int tmp = maxLocal; maxLocal = Max(Max(maxLocal * nums[i], nums[i]), minLocal * nums[i]); minLocal = Min(Min((tmp * nums[i]), nums[i]), minLocal * nums[i]); maxPro = Max(maxPro, maxLocal); } return maxPro; } }; 3 总结 多尝试，多思考。 第一题放在了分治算法的分支下，但个人觉得用分治算法太过于繁琐，在这道题里不适合，当然还是值得思考。