# Share my DP code that got AC

• ``````public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[] f = new int[A.length];
int[] g = new int[A.length];
f[0] = A[0];
g[0] = A[0];
int res = A[0];
for (int i = 1; i < A.length; i++) {
f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
res = Math.max(res, f[i]);
}
return res;
}
}
``````

f[i] means maximum product that can be achieved ending with i

g[i] means minimum product that can be achieved ending with i

• Did you forget to delete "f" and "g" at the end of the program?

• It's java, you do not need to worry about memory management.

• neat solution!!

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• This is O(n) space. Actually you can simply improve this to O(1) space by not storing f, g.

• Yes, you are right. The space complexity could be improved to O(1) by just keeping track of Min and Max. But it is not a big deal. Thanks for pointing that out!

• This post is deleted!

• Good Solution !!

• ^garbage collection

• Simple and elegant! :) But we don't need O(n) space as for every i we access only the i-1th element so, we can replace the 2 arrays with 2 variables.

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
int prevPos = nums[0];
int prevNeg = nums[0];
int ret = nums[0];
for(int i = 1; i < n; i++){
int pos = max(prevPos * nums[i], max(prevNeg * nums[i], nums[i]));
int neg = min(prevPos * nums[i], min(prevNeg * nums[i], nums[i]));
prevPos = pos;
prevNeg = neg;
ret = max(ret, pos);
}
return ret;
}
};
``````

• @harunrashidanver
Edit on your code removing redundant (costly) multiplication

``````int maxProduct(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
int prevPos = nums[0];
int prevNeg = nums[0];
int ret = nums[0];
for(int i = 1; i < n; i++){
int pos = prevPos * nums[i];
int neg = prevNeg * nums[i];
prevPos = max(nums[i], max(neg, pos));
prevNeg = min(nums[i], min(neg, pos));
ret = max(ret, prevPos);
}
return ret;
}
``````

• The easiest solution to understand. Thank you!

• What if the nums[i] == 0?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.