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.

s思路： 1. 先假設一些理想情況，當都是正數(shù)，最大積就是全部數(shù)相乘；如果有偶數(shù)個負數(shù)，也是全部相乘；如果有奇數(shù)個負數(shù)，那就要比較大小了，例如：nums=[-5,2,3,2-2,-4,2],就需要比較最左邊的負數(shù)與它之前的正數(shù)之積，即：-5，和最右邊的負數(shù)與它之后的正數(shù)之積，即：-4*2=-8，誰絕對值大，就那一邊。這里就是：-5之后的所有數(shù)相乘即是最大積。 2. 目前為止，我們只討論了正負數(shù)，還沒有討論0的情況。如果含有0，如何處理呢？想了一下，0的作用就是把這個序列分割成左右兩個array。所以，需要分別按照上面的方法求最大值，然后比較選出較大的最大值即可！ 3. 也就是說，這個題有o(n)的解法，因為每個數(shù)最多訪問一次即可！ 4. 上面的方法是可行，但寫起來很復雜，也不好理解。我們換一個角度重新思考。從左往右遍歷，我們計算包含當前正在遍歷的數(shù)的最大乘積和最小乘積，為什么要最小值呢？因為最小值，如果是負數(shù)，那么乘以一個負數(shù)，就是最大值了。但這個最小值和最大值每次和當前的數(shù)相乘是注意，如果當前數(shù)是正數(shù)，就是最大值乘以當前值仍然是最大值，最小值乘以當前值仍是最小值；如果當前值是負數(shù)，那么最大值就是之前的最小值乘這個負數(shù)，最小值就是之前的最大值乘這個負數(shù)；這還沒完，關(guān)鍵的一步是：得到最大最小值，還需要檢查是否最大最小，如果當前的遍歷的數(shù)比最大值還大或比最小值還小，那么就要更新最大值和最小值了，保證是最大值。 5. 上面的思路就是DP思路，就是一路記錄包含當前遍歷的數(shù)的最大乘積和最小乘積，然后取最大乘積的最大值即可！

6.問題來了，為什么這個方法比之前枚舉各種可能性的簡潔，而且好理解呢？這個方法是后面想到的，自己也想過要找最大值、最小值，但是沒定義清楚，比如：我們最后需要的最大最小值是包含當前num[i]的最大最小值，而不是從左往右一直乘的最大最小值。這兩者的區(qū)別是，前者在每次最大最小值，同時考慮了當前值是否比從左往右迭代過來的值還大或還小，由于每次算最大最小值，都考慮了這個信息，所以可以一直保證得到包含目前num[i]的最大最小值。而這個最大值的最大值即使所求！ 7. 之前想的第一種方法，只考慮了現(xiàn)象，試圖用代碼去模擬這個現(xiàn)象，還沒抓住本質(zhì)，因此深入不夠，沒有一個抽象的點在里面。而后面的方法，就是求包含num[i]的最大最小值，這就是把一個大的目標分割成小的目標，然后我們一直在這個小目標用功，大的目標也就得到了！本質(zhì)是問題的分割，由于問題可以分割，所以必然是dp.