Shortest C++ DP solution


#1

int Solution::maxProduct(const vector &A) {
int n = A.size();
int dp[n][2];
dp[0][0] = A[0];
dp[0][1] = A[0];
int ans = dp[0][0];
for(int i=1;i<n;i++){
dp[i][0] = max(dp[i-1][1]*A[i] , max(dp[i-1][0]*A[i] ,A[i]));
dp[i][1] = min(dp[i-1][1]*A[i] , min(dp[i-1][0]*A[i] ,A[i]));
ans = max(ans , dp[i][0]);
}
return ans;
}