一：Maximum Subarray
题目：
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.
链接：https://leetcode.com/problems/maximum-subarray/
分析：这题就是求最大连续字串的和，或者说是求和最大的连续子数组
此题最简单的是暴力，但是暴力为O(N^2)， 超时。另外可以采用动态规划来求解，关键是如何转换为动态规划问题，即如何表述成动态规划问题。
我们用local[i]来表示以A[i]结尾的连续子数组的最大和，那么local[0] = A[0],, local[1]等于要么local[0]+A[1] 要么就等于A[1]本身，，关键看两者谁更大，于是便得到递归式local[i+1] = max(local[i]+A[i], A[i]),,,,local数组中的最大值即为所求。 迭代的过程中无需数组 因此时间复杂度为O(N), 空间复杂度为O(1).
class Solution {public:int maxSubArray(int A[], int n) {if(n == 0) return 0;int sum = A[0];// 以A[0]结束的连续子数组和最大值int maxResult = A[0];for(int i = 1; i < n; i++){sum = max(A[i],A[i]+sum);// 以A[i]结束的连续子数组和最大值if(maxResult < sum) maxResult = sum;}return maxResult;}};
二：Maximum Product Subarray
题目：
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.
链接：https://leetcode.com/problems/maximum-product-subarray/
分析：此题我们不仅要保存一个最大值，还得保存一个最小值，因为负负相乘等于正数，比如-2 4 -5，即localMIn[i]表示以i结尾的连续字串乘积的最小值，而localMax[i]表示以i结尾的连续字串乘积的最大值，那么localMax[i] = max(max(localMin[i]*A[i], A[i]*localMax[i]), A[i]); 而localMin[i]=min(min(localMin[i]*A[i], A[i]*localMax[i]), A[i]);
class Solution {public:int maxProduct(int A[], int n) {if(n == 0) return 0;int result = A[0];int minProduct = A[0];int maxProduct = A[0];for(int i = 1; i < n; i++){int temp = max(A[i]*maxProduct, A[i]*minProduct);temp = max(temp, A[i]);minProduct = min(A[i]*maxProduct, A[i]*minProduct);minProduct = min(minProduct, A[i]);maxProduct = temp;result = max(maxProduct, result);}return result;}};
最快乐的时候，就是去旅行。
