I 找一个连续最大子数组，sum加到nums[i], 如果前面子数组和<0则舍去，从头开始。
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: A integer indicate the sum of max subarray 6 */ 7 int maxSubArray(vector<int> &nums) { 8 // write your code here 9 int ans=-0x3f3f3f3f,sum=0; 10 for(int i=0;i<nums.size();i++) 11 { 12 if(sum<0) 13 { 14 sum=nums[i]; 15 } 16 else sum+=nums[i]; 17 ans=max(ans,sum); 18 } 19 return ans; 20 } 21 };
II 找两个不重叠的子数组，使得他们的和最大。
思路：一般有了I，II是变形版本，想办法往I上套，因为小规模的I已经做出来了，要好好利用他。
枚举划分的位置，将数组划分为左右两部分，每一部分调用I的函数就行了
1 class Solution { 2 public: 3 /* 4 * @param nums: A list of integers 5 * @return: An integer denotes the sum of max two non-overlapping subarrays 6 */ 7 int maxTwoSubArrays(vector<int> &nums) { 8 // write your code here 9 vector<int> left(nums.size(), -0x3f3f3f3f); 10 vector<int> right(nums.size(), -0x3f3f3f3f); 11 int sum=-0x3f3f3f3f,ans=-0x3f3f3f3f; 12 for(int i=0;i<nums.size();i++) 13 { 14 if(sum<0) 15 sum = nums[i]; 16 else 17 sum+=nums[i]; 18 ans=max(ans,sum); 19 left[i]=ans; 20 } 21 sum=-0x3f3f3f3f; 22 ans=-0x3f3f3f3f; 23 for(int i=nums.size()-1;i>=0;i--) 24 { 25 if(sum<0) 26 sum = nums[i]; 27 else 28 sum+=nums[i]; 29 ans=max(ans,sum); 30 right[i]=ans; 31 } 32 ans=-0x3f3f3f3f; 33 for(int i=1;i<nums.size();i++) 34 { 35 ans=max(ans,left[i-1]+right[i]); 36 } 37 return ans; 38 } 39 };
III k个不重叠的子数组求其最大和
思路：
如何定义状态呢？一个状态必须包含题中所有信息，每一个状态都是独立不重复且覆盖每一种情况。
这样考虑，题干为一维数组，必须这样设计dp[i]，从而遍历每一个位置。考虑到k个不重叠的子数组这一条件，那么这样设计dp[i][j]=所求答案(最大和), 不一定包含结点i，这一dp[nums.size()-1][k]就是答案。
如何设计状态转移方程呢？考虑前一状态怎么转移到现在的，由于是二维dp，我们这样考虑取一个中间状态dp[i][j]，dp[i][j] = max( dp[i-1][j], )前一项是不加第i项，后一项要加第i项，
其中加第i项又分两种情况，第一种mustdp[i-1][j]+nums[i] 表示第i项并入第j个子数组, 第二种mustdp[i-1][j-1]+nums[i] 表示第i项独立成第j个子数组，为什么要新建一个数组mustdp，因为dp表示不一定包含最后一项，所以需要新建一个mustdp表示以最后一项结尾。综上所述：
mustdp[i][j] = max( dp[i-1][j-1] + nums[i]，must[i-1][j] + nums[i] );
dp[i][j] = (dp[i-1][j], mustdp[i][j] );
一定要注意初始化条件，有负数不能初始化为0，且不能溢出。循环的时候要遍历过所有情况才行。下面程序中dp表示一定以最后一个元素结尾，udp表示不一定
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @param k: An integer denote to find k non-overlapping subarrays 6 * @return: An integer denote the sum of max k non-overlapping subarrays 7 */ 8 int maxSubArray(vector<int> &nums, int k) { 9 // write your code here 10 11 for(int i=0;i<nums.size();i++) 12 for(int j=0;j<=k;j++) 13 { 14 udp[i][j]=-0x3f3f3f3f; // 注意防止溢出 15 dp[i][j]=-0x3f3f3f3f; 16 } 17 dp[0][0]=0; 18 udp[0][0]=0; 19 dp[0][1]=nums[0]; 20 udp[0][1]=nums[0]; 21 for(int i=1;i<nums.size();i++) 22 { 23 dp[i][0]=0; 24 udp[i][0]=0; 25 for(int j=1;j<=k;j++){ 26 27 dp[i][j] = max(udp[i-1][j-1]+nums[i],dp[i-1][j]+nums[i]); 28 udp[i][j] = max(udp[i-1][j],dp[i][j]); 29 } 30 } 31 return udp[nums.size()-1][k]; 32 } 33 int dp[1001][1001]; 34 int udp[1001][1001]; 35 };
第一维表示到前一位的位置，这样写就涵盖了dp[0][1]的初始化形式更加规范。
思路：记mustTheLast[i][j]为在前i个数中分成j段，且第j段必须有第i个数的最大值，notTheLast[i][j]为前i个中分成j段，且第j段不一定含有第i个数的最大值；注意初始化的数据，不能全部初始化为0，不然在全部为负整数以及一些其他情况的数组会出错；
动态规划方程为：
mustTheLast[i][j] = max(mustTheLast[i-1][j] + nums[i-1] ,notTheLast[i-1][j-1] + nums[i-1]);
notTheLast[i][j] = max(notTheLast[i-1][j] ,mustTheLast[i][j]);
1 class Solution { 2 public: 3 /* 4 * @param nums: A list of integers 5 * @param k: An integer denote to find k non-overlapping subarrays 6 * @return: An integer denote the sum of max k non-overlapping subarrays 7 */ 8 int maxSubArray(vector<int> &nums, int k) { 9 // write your code here 10 int n = nums.size(); 11 if(k > n) 12 return INT_MIN; 13 vector<vector<int> > notTheLast(n+1,vector<int>(k+1,-10000)); 14 vector<vector<int> > mustTheLast(n+1,vector<int>(k+1,-10000)); 15 mustTheLast[0][0] = 0; 16 notTheLast[0][0] = 0 ; 17 for(int i = 1 ; i <= n; i++) 18 { 19 mustTheLast[i][0] = 0 ; 20 notTheLast[i][0] = 0; 21 22 for(int j = 1 ; j <= k; j++) 23 { 24 mustTheLast[i][j] = max(mustTheLast[i-1][j] + nums[i-1] ,notTheLast[i-1][j-1] + nums[i-1]); 25 26 notTheLast[i][j] = max(notTheLast[i-1][j] ,mustTheLast[i][j]); 27 28 } 29 30 } 31 return notTheLast[n][k]; 32 33 } 34 };
IV 找一个最大子数组，且其长度大于k
简单题，思路：前缀和，只是这次preMin是在第一个到第i-k个数内部找而已。还是最大化sum[j] - sum[i]，就要求sum[i]一定要最小的，时间复杂度O(n)
V 找一个最大子数组，且其长度在区间[ k1, k2 ]
思路：看到区间类型的题，考虑维护一个最小(大)堆, 或类似形式的顺序队列，始终有序存储固定长度的候选值。
1 class Solution { 2 public: 3 /** 4 * @param nums an array of integers 5 * @param k1 an integer 6 * @param k2 an integer 7 * @return the largest sum 8 */ 9 int maxSubarray5(vector<int>& nums, int k1, int k2) { 10 // Write your code here 11 if (nums.size() < k1) { 12 return 0; 13 } 14 15 deque<int> dq; 16 vector<int> sum(nums.size()+1, 0); 17 int maxSum = -0x3f3f3f3f; 18 for(int i=1;i<=nums.size();i++) 19 { 20 sum[i] = sum[i-1] + nums[i-1]; 21 while(!dp.empty() && dp.front()<i-k2) 22 dp.pop_front(); 23 if(i>=k1) 24 { 25 while(!dp.empty() && sum[dp.back()]>sum[i-k1]) 26 dp.pop_back(); 27 dp.push_back(i-k1); 28 } 29 if(!dp.empty()) 30 maxSum = max(maxSum, sum[i]-sum[dp.front()]); 31 } 32 return maxSum; 33 } 34 };
Maximum Product Subarray 求最大子数组乘积
因为包含正数、负数、0。乘积比求和更加复杂。
f[i]表示以i结尾的最大子数组乘积
g[i]表示以i结尾的最小子数组乘积
整体是f[i] = 乘以nums[i](乘的时候又分正最大负最小的情况) 或者 nums[i]
1 class Solution { 2 public: 3 int maxProduct(vector<int>& nums) { 4 int res = nums[0], n = nums.size(); 5 vector<int> f(n, 0), g(n, 0); 6 f[0] = nums[0]; 7 g[0] = nums[0]; 8 for (int i = 1; i < n; ++i) { 9 f[i] = max(max(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]); 10 g[i] = min(min(f[i - 1] * nums[i], g[i - 1] * nums[i]), nums[i]); 11 res = max(res, f[i]); 12 } 13 return res; 14 } 15 };