coding-Interview/MaximumProductSubarray.java at master · arjunmullick/coding-Interview · GitHub

History

50 lines (41 loc) · 1.53 KB

Raw

package com.leetcode;

public class MaximumProductSubarray {

//https://leetcode.com/problems/maximum-product-subarray/

/**

Example 1:

Input: nums = [2,3,-2,4]

Output: 6

Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]

Output: 0

Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

**/

class Solution {

Many sub problem to simply took the pattern below.

// in once pass look for a max product of continious array from left to right

// in second pass look for a max product of continious array from right to left

// select max and return.

// Why it words ?

// it covers all continious array growing in either direction example input = [-2 1 3]-> [-2,-2,-6] and [3,3,-6] at each index we select max

int max;

public int maxProduct(int[] nums) {

max = Integer.MIN_VALUE;

int product = 1;

for(int i = 0 ; i < nums.length ; i++){

product = product * nums[i];

max = Math.max(max,product);

if(product == 0) product =1; //reset for next continious array

}

product = 1;//reset for right to left search

for(int i = nums.length-1 ; i>=0 ; i--){

product = product * nums[i];

max = Math.max(max,product);

if(product == 0) product =1;//reset for next continious array

}

return max;

}

coding-Interview/MaximumProductSubarray.java at master · arjunmullick/coding-Interview · GitHub

Expand file tree

Breadcrumbs

MaximumProductSubarray.java

Latest commit

History

Breadcrumbs

MaximumProductSubarray.java

File metadata and controls