[Java/2ms] One scan based on DP with explanation


  • 0

    when at index i,

    1. neg represents the smallest negative number from k to i-1, if exists. Otherwise, I set neg to be 0, meaning there's no negative number yet.

    2. pos means the biggest non-negative number [k, i-1]. If there's non-negative product, I set pos to be 1.

    public int maxProduct(int[] nums) {
            int neg = 0, pos = 1, max = nums[0];
            for (int num : nums) {
                if (num > 0) {
                    neg *= num;
                    // that is, pos == 0, take num as next maximum non-negative
                    pos = pos > 0 ? pos * num : num;
                    // for input can be [0, 1), since input are all integer, we can simplify it.
                    // pos = pos * num > num ? pos * num : num;
                    max = max > pos ? max : pos;
                } else { // num <= 0
                    int tmp = neg;
                    // for input can be [0, 1)
                    // neg = pos * num < num ? pos * num : num;
                    neg = pos > 0 ? pos * num : num;
                    if (tmp == 0) {
                        pos = 1;
                    } else {
                        pos = tmp * num;
                        max = pos > max ? pos : max;
                    }
                }
            }
            return max;
        }
    

Log in to reply
 

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