LeetCode 152. Maximum Product Subarray

题目链接 Maximum Product Subarray

相关题目 blog 地址

Continuous Subarray Sum

Subarray Sum Equals K

Subarray Product Less Than K



题意很简单,给定一个整数数组,找出它的最大的连续子数组的积

这题其实算DP 的题

里面其实蕴含一个状态和状态转移方程

假设原数组是A

状态B[i]表示以 A 中下标为 i 的位置结尾的最大连续子数组的乘积

状态C[i]表示以 A 中下标为 i 的位置结尾的最小连续子数组的乘积

其实可以得到状态转移方程

B[i] = max {B[i - 1] A[i] (i > 0 && A[i] > 0), A[i]}

B[i] = max {C[i - 1]
A[i] (i > 0 && A[i] < 0), A[i]}

C[i] = min {B[i - 1] A[i] (i > 0 && A[i] < 0), A[i]}

C[i] = min {C[i - 1]
A[i] (i > 0 && A[i] > 0), A[i]}

A[0] = B[0] = C[0]

talk is cheap, show you the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int maxProduct(int[] nums) {
int currentMax = nums[0];
int currentMin = nums[0];
int result = currentMax;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = currentMax;
currentMax = currentMin;
currentMin = temp;
}
currentMax = currentMax * nums[i] > nums[i] ? currentMax * nums[i] : nums[i];
if (currentMax > result) {
result = currentMax;
}
currentMin = currentMin * nums[i] < nums[i] ? currentMin * nums[i] : nums[i];
}
return result;
}
月月说要给我打赏,就还是放了二维码,😝