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. 這道題屬于動態規劃的題型，之前常見的是Maximum SubArray，現在是Product Subarray，不過思想是一致的。 當然不用動態規劃，常規方法也是可以做的，但是時間復雜度過高（TimeOut），像下面這種形式：
// 思路：用兩個指針來指向字數組的頭尾int maxProduct(int A[], int n){ assert(n > 0); int subArrayProduct = -32768; for (int i = 0; i != n; ++ i) { int nTempProduct = 1; for (int j = i; j != n; ++ j) { if (j == i) nTempProduct = A[i]; else nTempProduct *= A[j]; if (nTempProduct >= subArrayProduct) subArrayProduct = nTempProduct; } } return subArrayProduct;}用動態規劃的方法，就是要找到其轉移方程式，也叫動態規劃的遞推式，動態規劃的解法無非是維護兩個變量，局部最優和全局最優，我們先來看Maximum SubArray的情況，如果遇到負數，相加之后的值肯定比原值小，但可能比當前值大，也可能小，所以，對于相加的情況，只要能夠處理局部最大和全局最大之間的關系即可，對此，寫出轉移方程式如下： local[i + 1] = Max(local[i] + A[i], A[i]);
global[i + 1] = Max(local[i + 1], global[i]);
對應代碼如下：
int maxSubArray(int A[], int n){ assert(n > 0); if (n <= 0) return 0; int global = A[0]; int local = A[0]; for(int i = 1; i != n; ++ i) { local = MAX(A[i], local + A[i]); global = MAX(local, global); } return global;}而對于Product Subarray，要考慮到一種特殊情況，即負數和負數相乘：如果前面得到一個較小的負數，和后面一個較大的負數相乘，得到的反而是一個較大的數，如{2，-3，-7}，所以，我們在處理乘法的時候，除了需要維護一個局部最大值，同時還要維護一個局部最小值，由此，可以寫出如下的轉移方程式：
max_copy[i] = max_local[i] max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]), min_local * A[i])
min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]), min_local * A[i])
對應代碼如下：
#define MAX(x,y) ((x)>(y)?(x):(y))#define MIN(x,y) ((x)<(y)?(x):(y))int maxProduct1(int A[], int n){ assert(n > 0); if (n <= 0) return 0; if (n == 1) return A[0]; int max_local = A[0]; int min_local = A[0]; int global = A[0]; for (int i = 1; i != n; ++ i) { int max_copy = max_local; max_local = MAX(MAX(A[i] * max_local, A[i]), A[i] * min_local); min_local = MIN(MIN(A[i] * max_copy, A[i]), A[i] * min_local); global = MAX(global, max_local); } return global;}更加優化的代碼，空間復雜度降低為O(1)的代碼：
int maxProduct(vector<int>& nums) { int len = nums.size(); int maxherepre = nums[0]; int minherepre = nums[0]; int maxsofar = nums[0]; int maxhere, minhere; for(int i = 1; i < len; i++){ maxhere = max(max(maxherepre*nums[i],minherepre*nums[i]),nums[i]); minhere = min(min(maxherepre*nums[i],minherepre*nums[i]),nums[i]); maxsofar= max(maxsofar,maxhere); maxherepre = maxhere; minherepre = minhere; } return maxsofar; }總結：動態規劃題最核心的步驟就是要寫出其狀態轉移方程，但是如何寫出正確的方程式，需要我們不斷的實踐并總結才能達到。
新聞熱點
疑難解答
