【LeetCode】152.積最大サブシーケンス結題報告(C++)

原題住所:https://leetcode-cn.com/problems/maximum-product-subarray/description/
タイトルの説明:
整数配列numsが与えられ、少なくとも1つの数を含むシーケンスの積が最も大きい連続サブシーケンスが見出される.
例1:
入力:[2,3,−2,4]出力:6解釈:サブ配列[2,3]に最大積6がある.例2:
入力:[-2,0,-1]出力:0解釈:結果は2ではありません.[-2,-1]はサブ配列ではありません.
 
問題解決方案:
この問題の動的計画は明らかだが,学習に値するところは通項式の柔軟な運用である.ここでは、2つの数列を採用します.数列には正負の数があり、1つは最大値を記録し、もう1つは最小値を記録するために使用されます.
コード:

class Solution {
public:
    int maxProduct(vector& nums) {
        int f[nums.size()];
        int g[nums.size()];
        f[0] = nums[0];     //   
        g[0] = nums[0];     //   
        int ans = f[0];
        for (int i = 1; i < nums.size(); i++) {
            f[i] = max(f[i - 1] * nums[i], nums[i]);
            f[i] = max(g[i - 1] * nums[i], f[i]);
            g[i] = min(f[i - 1] * nums[i], nums[i]);
            g[i] = min(g[i - 1] * nums[i], g[i]);
            ans = max(ans, f[i]);
        }
        return ans;
    }
};