O(n) greedy solution


  • 0
    B
    public class Solution {
        public int Solve(int[] nums) {
            int curr = Integer.MIN_VALUE,mx = Integer.MIN_VALUE;
            boolean has_neg [] = new boolean [nums.length];
            boolean f = false;
            for(int i = nums.length-1 ;i >= 0;i--){
                if(nums[i] == 0)
                    f = false;
                has_neg[i] = f;
                f|=(nums[i] < 0);
            }
            
            f = false;
                    
            for(int i = 0;i < nums.length;i++){
                if(nums[i] < 0){
                    if(f){
                        nums[i]*=-1;
                        f = false;
                    }else if(has_neg[i]){
                        f = true;
                        nums[i]*=-1;
                    }
                }
                if(curr != Integer.MIN_VALUE){
                    curr = Math.max(nums[i],curr*nums[i]);
                }else curr = nums[i];
                mx = Math.max(mx,curr);
            }
            return mx;
        }
        public int maxProduct(int[] nums) {
            int nums2[] = new int [nums.length];
            for(int i = 0,j = nums.length-1; i < nums.length;i++,j--)
                nums2[j] = nums[i];
            return Math.max(Solve(nums),Solve(nums2));
        }
    }
    

Log in to reply
 

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