难度简单
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入:[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
分析：题目是从一个数组中找到最大和的连续子数组，是一个求最值的问题。当遇到求最值的问题，首先想到如何把所有的可能的结果穷举出来。当数组长度为一的时候（此时为array1），答案就是本身，当长度为2时，就是求长度为2的数组的最大字串（array2）...此时应该敏锐的观察到，穷举出array2的子串时会与array1重叠一次。所以为了更高效的穷举，我们应该规定穷举出的子串末尾必须是当前的array[2]，而前面则是之前array1穷举的最大子串。在这个过程中其实可以发现这就是一个动态规划的问题，而状态转移方程可以写为dp = max(dp + nums[i], nums[i]);
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int numSize = nums.size();
int dp(nums[0]);
res = dp;
for(int i = 1; i < numSize; ++i){
dp = max(dp + nums[i], nums[i]);
res = max(dp, res);
}
return res;
}
};
难度中等
给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入:[2,3,-2,4]输出:6解释:子数组 [2,3] 有最大乘积 6。
示例 2:
输入:[-2,0,-1]输出:0解释:结果不能为 2, 因为 [-2,-1] 不是子数组。
分析：这道题如果有上道题的基础，那么要思考的点就会大大减少了。和上道题不同的是，这里是乘积，当自底向上解决问题的时候，最后一位的数可能为负数。当为负数的时候，显然按照上一道题的做法（将加改成乘），就出现了错误。所以这里在之前存储最大乘积的基础值之上，也要存储最小乘积（一般为负值）。【PS:我竟然能想到同时存储最小乘积，真是有点进步了哈哈😄】当 当前数组最后一位元素为负时，最大乘积为之前乘积最小值乘以现在的负值。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int numSize = nums.size();
int dpMax = 1, dpMin = 1;
int res = INT_MIN;
for(int i = 0; i < numSize; ++i){
if(nums[i] < 0){
int temp = dpMax;
dpMax = dpMin;
dpMin = temp;
}
dpMax = max(dpMax * nums[i], nums[i]);
dpMin = min(dpMin * nums[i], nums[i]);
res = max(dpMax, res);
}
return res;
}
};
刚开始做动态规划的题，感觉自己理解的不够深入，表达也很不清楚。等之后理解深入的时候，再修改修改吧。😀
