-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaxSubarray.cpp
116 lines (93 loc) · 3.89 KB
/
MaxSubarray.cpp
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
Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
这题是一道经典的dp问题,我们可以很容易的得到其dp方程,假设dp[i]是数组a [0, i]区间最大的值,那么
dp[i + 1] = max(dp[i], dp[i] + a[i + 1])
代码如下:
class Solution {
public:
int maxSubArray(int A[], int n) {
int sum = 0;
int m = INT_MIN;
for(int i = 0; i < n; i++) {
sum += A[i];
m = max(m, sum);
//如果sum小于0了,将sum重置为0,从i + 1再次开始计算
if(sum < 0) {
sum = 0;
}
}
return m;
}
};
虽然这道题目用dp解起来很简单,但是题目说了,问我们能不能采用divide and conquer的方法解答,也就是二分法。
假设数组A[left, right]存在最大区间,mid = (left + right) / 2,那么无非就是三中情况:
最大值在A[left, mid - 1]里面
最大值在A[mid + 1, right]里面
最大值跨过了mid,也就是我们需要计算[left, mid - 1]区间的最大值,以及[mid + 1, right]的最大值,然后加上mid,三者之和就是总的最大值
我们可以看到,对于1和2,我们通过递归可以很方便的求解,然后在同第3的结果比较,就是得到的最大值。
代码如下:
class Solution {
public:
int maxSubArray(int A[], int n) {
return divide(A, 0, n - 1, INT_MIN);
}
int divide(int A[], int left, int right, int tmax) {
if(left > right) {
return INT_MIN;
}
int mid = left + (right - left) / 2;
//得到子区间[left, mid - 1]最大值
int lmax = divide(A, left, mid - 1, tmax);
//得到子区间[mid + 1, right]最大值
int rmax = divide(A, mid + 1, right, tmax);
tmax = max(tmax, lmax);
tmax = max(tmax, rmax);
int sum = 0;
int mlmax = 0;
//得到[left, mid - 1]最大值
for(int i = mid - 1; i >= left; i--) {
sum += A[i];
mlmax = max(mlmax, sum);
}
sum = 0;
int mrmax = 0;
//得到[mid + 1, right]最大值
for(int i = mid + 1; i <= right; i++) {
sum += A[i];
mrmax = max(mrmax, sum);
}
tmax = max(tmax, A[mid] + mlmax + mrmax);
return tmax;
}
};
Maxmimum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
这题是求数组中子区间的最大乘积,对于乘法,我们需要注意,负数乘以负数,会变成正数,所以解这题的时候我们需要维护两个变量,当前的最大值,以及最小值,最小值可能为负数,但没准下一步乘以一个负数,当前的最大值就变成最小值,而最小值则变成最大值了。
我们的动态方程可能这样:
maxDP[i + 1] = max(maxDP[i] * A[i + 1], A[i + 1], minDP[i] * A[i + 1])
minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1], maxDP[i] * A[i + 1]
dp[i + 1] = max(dp[i], maxDP[i + 1])
这里,我们还需要注意元素为0的情况,如果A[i]为0,那么maxDP和minDP都为0,我们需要从A[i + 1]重新开始。
代码如下:
class Solution {
public:
int maxProduct(int A[], int n) {
if(n == 0){
return 0;
} else if(n == 1) {
return A[0];
}
int p = A[0];
int maxP = A[0];
int minP = A[0];
for(int i = 1; i < n; i++) {
int t = maxP;
maxP = max(max(maxP * A[i], A[i]), minP * A[i]);
minP = min(min(t * A[i], A[i]), minP * A[i]);
p = max(maxP, p);
}
return p;
}
};