My naive java solution, runtime beats 90+%.


  • 0
    L

    It looks naive but easy to understand.

    class Solution {
        public int findFirstNeg(int[] nums, int idx){
            int i = idx - 1;
            for(; i >= 0 && nums[i] > 0; i--);
            return (i >= 0) ? i : idx;
        }
        public int maxProduct(int[] nums) {
            int n = nums.length;
            int[] record = new int[n];
            record[0] = nums[0];
            int res = record[0];
            for(int i = 1; i < n; i++){
                if(nums[i] > 0 && record[i - 1] > 0)
                    record[i] = record[i - 1] * nums[i];
                else if(nums[i] > 0 && record[i - 1] <= 0)
                    record[i] = nums[i];
                else if(nums[i] < 0 && record[i - 1] < 0)
                    record[i] = record[i - 1] * nums[i];
                else{
                    int idx = findFirstNeg(nums, i);
                    int product = 1;
                    for(int j = idx; j <= i; j++)
                        product *= nums[j];
                    if(idx > 0 && record[idx - 1] > 0)
                        product *= record[idx - 1];
                    record[i] = product;
                }
                res = Math.max(res, record[i]);
            }
            return res;
        }
    }
    

Log in to reply
 

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