FilesExpand file tree

 master

/

152_MaximumProductSubarray152.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

131 lines (121 loc) · 4.17 KB

 master

/

152_MaximumProductSubarray152.java

Copy path

Top

File metadata and controls

• Code
• Blame

131 lines (121 loc) · 4.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

/**

* Given an integer array nums, find the contiguous subarray within an array

* (containing at least one number) which has the largest product.

*

* Example 1:

* Input: [2,3,-2,4]

* Output: 6

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

*

* Example 2:

* Input: [-2,0,-1]

* Output: 0

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

*/

public class MaximumProductSubarray152 {

// time O(n), space O(n)

public int maxProduct(int[] nums) {

if (nums == null || nums.length == 0) return 0;

int len = nums.length;

if (len == 1) return nums[0];

boolean hasZero = false;

int[] pos = new int[len+1];

int[] neg = new int[len+1];

int res = Integer.MIN_VALUE;

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

int now = nums[i];

if (now > 0) {

pos[i+1] = pos[i] == 0 ? now : pos[i] * now;

neg[i+1] = neg[i] == 0 ? 0 : neg[i] * now;

} else if (now < 0) {

pos[i+1] = neg[i] == 0 ? 0 : neg[i] * now;

neg[i+1] = pos[i] == 0 ? now : pos[i] * now;

} else {

hasZero = true;

}

if (pos[i+1] != 0 && pos[i+1] > res) {

res = pos[i+1];

}

if (neg[i+1] != 0 && neg[i+1] > res) {

res = neg[i+1];

}

}

return (hasZero && res < 0) ? 0 : res;

}

// time O(n), space O(1)

public int maxProduct2(int[] nums) {

if (nums == null || nums.length == 0) return 0;

int len = nums.length;

if (len == 1) return nums[0];

boolean hasZero = false;

int pos = 0;

int neg = 0;

int res = Integer.MIN_VALUE;

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

int now = nums[i];

int oldPos = pos;

int oldNeg = neg;

if (now > 0) {

pos = oldPos == 0 ? now : oldPos * now;

neg = oldNeg == 0 ? 0 : oldNeg * now;

} else if (now < 0) {

pos = oldNeg == 0 ? 0 : oldNeg * now;

neg = oldPos == 0 ? now : oldPos * now;

} else {

hasZero = true;

pos = 0;

neg = 0;

}

if (pos != 0 && pos > res) {

res = pos;

}

if (neg != 0 && neg > res) {

res = neg;

}

}

return (hasZero && res < 0) ? 0 : res;

}

/**

* https://leetcode.com/problems/maximum-product-subarray/discuss/48330/Simple-Java-code

*/

public int maxProduct3(int[] A) {

if (A == null || A.length == 0) {

return 0;

}

int max = A[0], min = A[0], result = A[0];

for (int i = 1; i < A.length; i++) {

int temp = max;

max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);

min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);

if (max > result) {

result = max;

}

}

return result;

}

/**

* https://leetcode.com/problems/maximum-product-subarray/discuss/48230/Possibly-simplest-solution-with-O(n)-time-complexity

*/

public int maxProduct4(int A[]) {

// store the result that is the max we have found so far

int r = A[0];

// imax/imin stores the max/min product of

// subarray that ends with the current number A[i]

for (int i = 1, imax = r, imin = r; i < A.length; i++) {

// multiplied by a negative makes big number smaller, small number bigger

// so we redefine the extremums by swapping them

if (A[i] < 0) {

int t = imax;

imax = imin;

imin = t;

}

// max/min product for the current number is either the current number itself

// or the max/min by the previous number times the current one

imax = Math.max(A[i], imax * A[i]);

imin = Math.min(A[i], imin * A[i]);

// the newly computed max value is a candidate for our global result

r = Math.max(r, imax);

}

return r;

}

}