What if there is overflow?


  • 0
    Z

    I'd share my solution which is easy to extend to solve the problem if the product itself could be overlarge and only needs to return the max segment.

    Basically, if we divide the array to non-zero segments. For each segment, the max product can only be

    1. if there are even number of negatives, the max is the whole segment
    2. if there are odd number of negatives, the max is either the half after the first neg, or the half before the last neg
    3. one corner case is there is only one negative, the max is the neg itself.

    So we can record all the candidates in one pass. Then need to get the max one.
    In below solution, I use the trivial solution to get the largest product. However, if there is overflow, it is doable (but very tricky) to get the max without calculating the actual product.

    public int maxProduct(int[] A) {
        ArrayList<int[]> segs = new ArrayList<int[]>();
        int start = 0;
        boolean has0 = false;
        while (start < A.length) {
            while (start < A.length && A[start] == 0) start ++;
            has0 |= start > 0;
            
            int end = start;
            int cntNeg = 0;
            int firstNeg = -1;
            int lastNeg = -1;
            while (end < A.length && A[end] != 0) {
                if (A[end] < 0) {
                    if (firstNeg == -1) firstNeg = end;
                    lastNeg = end;
                    cntNeg ++;
                }
                end ++;
            }
            has0 |= end < A.length;
            
            if (cntNeg % 2 == 0 || start==end-1) {
                add(segs, start, end-1);
            } else {
                add(segs, start, lastNeg-1);
                add(segs, firstNeg+1, end-1);
            }
            start = end;
        }
        return has0 ? Math.max(0, max(segs, A)) : max(segs, A);
    }
    
    private int max(ArrayList<int[]> al, int[] A) {
        int max = Integer.MIN_VALUE;
        for (int[] seg : al) {
            int pro = 1;
            for (int i=seg[0]; i<=seg[1]; i++) {
                pro *= A[i];
            }
            max = Math.max(max, pro);
        }
        return max;
    }
    
    void add(ArrayList<int[]> al, int start, int end) {
        if (start > end) return;
        int[] i2 = new int[2];
        i2[0] = start; i2[1] = end;
        al.add(i2);
    }

  • 0
    F

    Hi, zhangxian97.

    Thanks for sharing your solution. For the second case when there are odd number of negative integers, I think you should also need to include the half before the first negative and the half after the last negative for candidates of maximum product.


  • 0
    Z

    No as long as numbers are ints, it's not.


Log in to reply
 

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