I 找一个连续最大子数组，sum加到nums[i], 如果前面子数组和<0则舍去，从头开始。
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> &nums) {
// write your code here
int ans=-0x3f3f3f3f,sum=;
for(int i=;i<nums.size();i++)
{
if(sum<)
{
sum=nums[i];
}
else sum+=nums[i];
ans=max(ans,sum);
}
return ans;
}
};
II 找两个不重叠的子数组，使得他们的和最大。
思路：一般有了I，II是变形版本，想办法往I上套，因为小规模的I已经做出来了，要好好利用他。
枚举划分的位置，将数组划分为左右两部分，每一部分调用I的函数就行了
class Solution {
public:
/*
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
int maxTwoSubArrays(vector<int> &nums) {
// write your code here
vector<int> left(nums.size(), -0x3f3f3f3f);
vector<int> right(nums.size(), -0x3f3f3f3f);
int sum=-0x3f3f3f3f,ans=-0x3f3f3f3f;
for(int i=;i<nums.size();i++)
{
if(sum<)
sum = nums[i];
else
sum+=nums[i];
ans=max(ans,sum);
left[i]=ans;
}
sum=-0x3f3f3f3f;
ans=-0x3f3f3f3f;
for(int i=nums.size()-;i>=;i--)
{
if(sum<)
sum = nums[i];
else
sum+=nums[i];
ans=max(ans,sum);
right[i]=ans;
}
ans=-0x3f3f3f3f;
for(int i=;i<nums.size();i++)
{
ans=max(ans,left[i-]+right[i]);
}
return ans;
}
};
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表示不一定
class Solution {
public:
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxSubArray(vector<int> &nums, int k) {
// write your code here
for(int i=;i<nums.size();i++)
for(int j=;j<=k;j++)
{
udp[i][j]=-0x3f3f3f3f; // 注意防止溢出
dp[i][j]=-0x3f3f3f3f;
}
dp[][]=;
udp[][]=;
dp[][]=nums[];
udp[][]=nums[];
for(int i=;i<nums.size();i++)
{
dp[i][]=;
udp[i][]=;
for(int j=;j<=k;j++){
dp[i][j] = max(udp[i-][j-]+nums[i],dp[i-][j]+nums[i]);
udp[i][j] = max(udp[i-][j],dp[i][j]);
}
}
return udp[nums.size()-][k];
}
int dp[][];
int udp[][];
};
第一维表示到前一位的位置，这样写就涵盖了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]);
class Solution {
public:
/*
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxSubArray(vector<int> &nums, int k) {
// write your code here
int n = nums.size();
if(k > n)
return INT_MIN;
vector<vector<int> > notTheLast(n+,vector<int>(k+,-));
vector<vector<int> > mustTheLast(n+,vector<int>(k+,-));
mustTheLast[][] = ;
notTheLast[][] = ;
for(int i = ; i <= n; i++)
{
mustTheLast[i][] = ;
notTheLast[i][] = ;
for(int j = ; j <= k; j++)
{
mustTheLast[i][j] = max(mustTheLast[i-][j] + nums[i-] ,notTheLast[i-][j-] + nums[i-]);
notTheLast[i][j] = max(notTheLast[i-][j] ,mustTheLast[i][j]);
}
}
return notTheLast[n][k];
}
};
IV 找一个最大子数组，且其长度大于k
简单题，思路：前缀和，只是这次preMin是在第一个到第i-k个数内部找而已。还是最大化sum[j] - sum[i]，就要求sum[i]一定要最小的，时间复杂度O(n)
V 找一个最大子数组，且其长度在区间[ k1, k2 ]
思路：看到区间类型的题，考虑维护一个最小(大)堆, 或类似形式的顺序队列，始终有序存储固定长度的候选值。
class Solution {
public:
/**
* @param nums an array of integers
* @param k1 an integer
* @param k2 an integer
* @return the largest sum
*/
int maxSubarray5(vector<int>& nums, int k1, int k2) {
// Write your code here
if (nums.size() < k1) {
return ;
}
deque<int> dq;
vector<int> sum(nums.size()+, );
int maxSum = -0x3f3f3f3f;
for(int i=;i<=nums.size();i++)
{
sum[i] = sum[i-] + nums[i-];
while(!dp.empty() && dp.front()<i-k2)
dp.pop_front();
if(i>=k1)
{
while(!dp.empty() && sum[dp.back()]>sum[i-k1])
dp.pop_back();
dp.push_back(i-k1);
}
if(!dp.empty())
maxSum = max(maxSum, sum[i]-sum[dp.front()]);
}
return maxSum;
}
};
Maximum Product Subarray 求最大子数组乘积
因为包含正数、负数、0。乘积比求和更加复杂。
f[i]表示以i结尾的最大子数组乘积
g[i]表示以i结尾的最小子数组乘积
整体是f[i] = 乘以nums[i](乘的时候又分正最大负最小的情况) 或者 nums[i]
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[], n = nums.size();
vector<int> f(n, ), g(n, );
f[] = nums[];
g[] = nums[];
for (int i = ; i < n; ++i) {
f[i] = max(max(f[i - ] * nums[i], g[i - ] * nums[i]), nums[i]);
g[i] = min(min(f[i - ] * nums[i], g[i - ] * nums[i]), nums[i]);
res = max(res, f[i]);
}
return res;
}
};