05 August 2008
DP, 同152 - Maximum Product Subarray类似，维护正负两个子数组
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
class Solution {
// dp[i] - 到i位置时最长正prodcut的子数组
// DP[i] = if nums[i] == 0, skip nums[i];
// if nums[i] > 0, max value subarray, len + 1
// if nums[i] < 0, min value subarray, len + 1
public int getMaxLen(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
// 第一个数字为default，也可以不用+1
long[] positives = new long[len + 1];
long[] negatives = new long[len + 1];
long result = 0;
for (int i = 1; i <= len; i++) {
if (nums[i - 1] == 0) {
positives[i] = 0;
negatives[i] = 0;
} else if (nums[i - 1] > 0) {
positives[i] = positives[i - 1] + 1;
negatives[i] = negatives[i - 1] == 0 ? 0 : negatives[i - 1] + 1;
} else {
// 注意这里nums[i]是负数的话，正数积子数组是从前一个负数积子数组中来，负负得正
positives[i] = negatives[i - 1] == 0 ? 0 : negatives[i - 1] + 1;
// 同样正负得负
negatives[i] = positives[i - 1] + 1;
}
result = Math.max(result, positives[i]);
}
return (int)result;
}
}
状态压缩
1
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
class Solution {
public int getMaxLen(int[] nums) {
int n = nums.length;
// 负、正数个数 第一个负数出现的位置
int neg = 0, pos = 0, fisrt = -1;
int ans = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
// 遇到0所有标记初始化
pos = 0;
neg = 0;
fisrt = -1;
} else if (nums[i] > 0) {
pos++;
} else {
// 记录该段第一个负数出现的位置
if (fisrt == -1) {
fisrt = i;
}
neg++;
}
if (neg % 2 == 0) {
// 该段所有数乘积为正
ans = Math.max(ans, pos + neg);
} else {
// 从第一个负数出现的位置后面到当前位置的乘积为正
ans = Math.max(ans, i - fisrt);
}
}
return ans;
}
}