53. Maximum Subarray
之前的值小于0就不加了。dp[i]表示以i结尾当前的最大和，所以需要用一个变量保存最大值。
动态规划的方法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size());
int res = INT_MIN;
for(int i = ;i < nums.size();i++){
dp[i] = nums[i];
if(i > && dp[i-] >= )
dp[i] += dp[i-];
res = max(res,dp[i]);
}
return res;
}
};
152. Maximum Product Subarray
最小值可能是负数，这个值可能变成最大值。
dp[i]表示以i结尾当前的最大乘积，所以需要用一个变量保存最大值。
为什么每次要与nums[i]做对比，因为数组中可能存在0
动态规划的方法：
class Solution {
public:
int maxProduct(vector<int>& nums) {
vector<int> dp_max(nums.size());
vector<int> dp_min(nums.size());
dp_max[] = nums[];
dp_min[] = nums[];
int res = nums[];
for(int i = ;i < nums.size();i++){
dp_max[i] = max(dp_max[i-] * nums[i],max(dp_min[i-] * nums[i],nums[i]));
dp_min[i] = min(dp_max[i-] * nums[i],min(dp_min[i-] * nums[i],nums[i]));
res = max(res,dp_max[i]);
}
return res;
}
};
非动态规划，节省空间的方法：
https://blog.csdn.net/whuwangyi/article/details/39577455解法3
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max = nums[];
int pre_max = nums[],pre_min = nums[];
int cur_max,cur_min;
for(int i = ;i < nums.size();i++){
cur_max = compare_max(pre_max*nums[i],pre_min*nums[i],nums[i]);
cur_min = compare_min(pre_max*nums[i],pre_min*nums[i],nums[i]);
pre_max = cur_max;
pre_min = cur_min;
max = cur_max > max ? cur_max : max;
}
return max;
}
int compare_max(int a,int b,int c){
int max = a;
if(b > max)
max = b;
if(c > max)
max = c;
return max;
}
int compare_min(int a,int b,int c){
int min = a;
if(b < min)
min = b;
if(c < min)
min = c;
return min;
}
};