# Clear DP solution, confused by the time cost

• I am confused by the time cost of my two solutions.
In the first one I use two vectors to save information and in the second one I just use 4 integers to do the same work. The idea is very similar to shinichish's solution

The first version is shown as followed:

Code in this version costs 20ms

``````int maxProduct(int A[], int n) {
if(!n) return 0;
int product = 0;
vector<int> maxVal(n, 0);
vector<int> minVal(n, 0);
maxVal[0] = minVal[0] = A[0];
for(int i=1; i<n; i++) {
maxVal[i] = max(A[i], max(A[i]*maxVal[i-1], A[i]*minVal[i-1]));
minVal[i] = min(A[i], min(A[i]*maxVal[i-1], A[i]*minVal[i-1]));
}
int result = INT_MIN;
for(int i : maxVal)
result = max(result, i);
return result;
}
``````

Then I prove my code and replace the vectors with 4 integers. Thus in this version the memory complexity is O(1).

Code in this version costs 40ms

``````int maxProduct(int A[], int n) {
if(!n) return 0;
int lastMaxVal = A[0], lastMinVal = A[0], maxPro = A[0];
int curMaxVal, curMinVal;
for(int i=1; i<n; i++) {
curMaxVal = max(A[i], max(A[i]*lastMaxVal, A[i]*lastMinVal));
curMinVal = min(A[i], min(A[i]*lastMaxVal, A[i]*lastMinVal));
lastMaxVal = curMaxVal; lastMinVal = curMinVal;
maxPro = max(maxPro, curMaxVal);
}
return maxPro;
}
``````