动态规划。
dp[0][i]: A[0, …, i-1]的maximum product subarray,
dp[1][i]: A[0, …, i-1)的minimum product subarray.
初始化dp[0][0] = dp[1][0] = A[0].
递推公式:
dp[0][i] = max(dp[0][i-1]*A[i], dp[1][i-1]*A[i]);dp[0][i] = max(dp[0][i], A[i]);dp[1][i] = min(dp[0][i-1]*A[i], dp[1][i-1]*A[i]);dp[1][i] = min(dp[1][i], A[i]);
代码:
class Solution {public:int maxProduct(int A[], int n){int dp[2][n];dp[0][0] = A[0];dp[1][0] = A[0];for (int i = 1; i < n; ++ i){dp[0][i] = max(dp[0][i-1]*A[i], dp[1][i-1]*A[i]);dp[0][i] = max(dp[0][i], A[i]);dp[1][i] = min(dp[0][i-1]*A[i], dp[1][i-1]*A[i]);dp[1][i] = min(dp[1][i], A[i]);}return *max_element(dp[0], dp[0]+n);}};
,这一次是一个告别,或者一个永远的告别,