Share my DP code that got AC


  • 43
    S
    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


  • -12
    Y

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


  • 1
    O

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


  • 0
    E

    neat solution!!


  • 0
    S
    This post is deleted!

  • 1
    S

    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


  • 0
    S

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


  • 0
    S

    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!


  • 0
    H
    This post is deleted!

  • 0
    S

    From all AC answers that I read, your solution was the easiest to understand. Thanks!


  • 0
    E

    Good Solution !!


  • 0
    P

    ^garbage collection


  • 2
    H

    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;
        }
    };
    

  • 0
    M

    @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;
        }
    

  • 0
    F

    The easiest solution to understand. Thank you!


  • 0
    B

    What if the nums[i] == 0?


Log in to reply
 

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