My Java Solution With DP in 5ms


  • 0
    B
    public int maxProduct(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int[][] dp = new int[nums.length + 1][2];
            dp[0][0] = nums[0];
            dp[0][1] = 0;
            int max = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i][0] = nums[i]>=0?nums[i]:0;
                dp[i][1] = nums[i]<=0?nums[i]:0;
                for (int j = 0; j < 2; j++) {
                    int tmp = dp[i - 1][j] * nums[i];
                    if (tmp >= 0) {
                        dp[i][0] = Math.max(tmp, dp[i][0]);
                        if (dp[i][0] > max) max = dp[i][0];
                    } else {
                        dp[i][1] = Math.min(tmp, dp[i][1]);
                        if (dp[i][1] > max) max = dp[i][1];
                    }
                }
            }
            return max;
        }

Log in to reply
 

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