今天沉迷愛的迫降，好在這道題不難，不然要做到深夜了。
題目雖然不難，但是是一道非常經典的dp，回顧總結一下對dp的了解
Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
dp的思想其實和數學歸納法、RNN有很多類似的地方，出發點都是：怎麼從n -> n+1？怎麼利用前一個checkpoint的信息？
回到這道題本身，實現O(n)我的第一層思路是「每個點上紀錄一個以該點結尾的最大product」，然後用一個cur_max在迭代過程中不斷更新最後輸出
往第二層思路入點是n+1點上的最大product，是怎麼從n點計算過來的？需要哪些信息？於是想到如果n+1處是正數就直接乘，如果是負，那麼應當是「n處的負「最大絕對值」乘積」，那麼很自然，一開始需要儲存的是「以該點結尾的正最大product和負最大product，最大的含義為絕對值」
一些修補和細節增添之後就有了如下非常淺顯的代碼。在coding這邊，我的理解還算很淺，有兩句話我是一直當作座右銘：
其一，talk is cheap - show me the code。有時候話說的再多不如直接代碼直觀。其二，premature optimization is the root of all evil。尤其是做網申題，思路要清晰，pseudo code轉化成代碼的過程中除非有bug儘量不優化，忍住優化的欲望記下筆記跑通之後再優化，不然有可能前後思路或者某個變量的使用不一致。
下面這個代碼我是一遍跑通的沒有bug，看著醜但是思路還可以，只有一個corner case在於數組只有一個負數的時候，其實和我對於兩個輔助容器的定義有問題（歸0的地方），所以我單獨列出來了
class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
int n = nums.size();
int pos[n];
int neg[n];
pos[0] = nums[0] > 0 ? nums[0] : 0;
neg[0] = nums[0] < 0 ? nums[0] : 0;
int cur_max = pos[0];
for (int i = 1; i < n; i++){
if (nums[i] > 0){
if(pos[i-1] > 0) pos[i] = pos[i-1] * nums[i];
else pos[i] = nums[i];
if(neg[i-1] < 0) neg[i] = neg[i-1] * nums[i];
else neg[i] = 0;
}
else if (nums[i] == 0){
pos[i] = 0;
neg[i] = 0;
}
else{//nums[i] < 0
if (neg[i-1] < 0) pos[i] = neg[i-1] * nums[i];
else pos[i] = 0;
if (pos[i-1] > 0) neg[i] = pos[i-1] * nums[i];
else neg[i] = nums[i];
}
cur_max = pos[i] > cur_max ? pos[i] : cur_max;
//cout << i << '|' << pos[i] << '|' << neg[i] << endl;
}
return cur_max;
}
};
很明顯，pos[i]和neg[i]只用到了pos[i-1]和neg[i-1]，沒必要用容器，直接用變量，實現O(1)空間佔用
可以直接維護max和min。。。fmax[i] = max(fmax[i-1] * nums[i], fmin[i-1] * nums[i], nums[i])，這個思路就顯得我很菜
class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.size(); ++i) {
int mx = maxF, mn = minF;
maxF = max(mx * nums[i], max(nums[i], mn * nums[i]));
minF = min(mn * nums[i], min(nums[i], mx * nums[i]));
ans = max(maxF, ans);
}
return ans;
}
};
//作者：LeetCode-Solution
//連結：https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
//來源：力扣（LeetCode）
//著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。