最大子数组问题：有数组P，长为n，求max(P[j] - P[i])
穷举法
即从第一个数i开始，依次加一，并将结果 A[i + 1]存入数组，然后我们会得到一个有 [n*(n-1)] 个元素的数组， 数组中的最大值就是我们要的结果。
注意此处我们是把已经加过的数存入数组，以供后面的加使用，不必再重新相加计算。
总结：此方法太耗时（时间复杂度为 n^2），且占用大量空间，pass！
差分法（分治法）
例存在数组 A[7,9,2,11,6,4,15,3,8]，我们将A[i - (i-1)]存入另一数组S
所以，我们成功的将寻找A的最大子数组分解为寻找S，步骤如下：
- 分：将原数组拆分为两部分，每部分再拆分为新的两部分….直至数组剩下一个元素
- 治：每个小型的数组寻找最大子数组（若数组只有一个元素，那么就是这个元素）
- 合：将左右两部分的的小型数组合并，其中解有三种可能：
- 左边返回值大
- 右边返回值大
- 中间存在一个更大的数组
- 以中点为初始，分别向两边扩散并相加
Divide方法 ：此方法主要是将数组切割，直至数组中只有一个元素。然后，进行左右中三侧数组返回的最大值对比，并返回三者最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static int Divide(int[] arrs, int left, int right) {
//当被划分数组只有一个元素时
if(left == right){
return arrs[left];
}else{
int mid = (left + right)/2;
int l_max = Divide(arrs, left, mid); //最大子数组位于左侧
int r_max = Divide(arrs, mid+1, right); //最大子数组位于右侧
int m_max = MiddleMax(arrs, left, mid, right); //最大子数组跨越中点的情况
//左侧返回值最大
if(l_max >= r_max && l_max>=m_max){
return l_max;
}else if (r_max >= l_max && r_max >= m_max){
//右侧返回值最大
return r_max;
}else{
//跨越中点返回值最大
return m_max;
}
}
}
MiddleMax方法：此方法是用来寻找跨越中点的最大子数组情况。思路是首先以中点为界，分为左右两侧。以左侧为例，由mid逐步向左推荐并相加，将sum和left_max对比，若大于，那么更新left_max，否则不更新。右侧同理，最后将左右两侧最大值相加并返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static int MiddleMax(int[] arr, int left, int mid, int right) {
int sum = 0;
int l_max = 0;
for (int i = mid; i >= left; i--) {
sum +=arr[i]; //将子数组元素一次相加
if( sum >= l_max){ //与l_max进行比较，若大于，则替换
l_max = sum;
}
}
//右侧同理
sum = 0; //sun归零
int r_max= 0;
for (int i = mid+1; i <= right; i++) {
sum += arr[i];
if( sum >= r_max){
r_max = sum;
}
}
return (l_max + r_max);
}
main：主方法，主要是将原数组转化为差数组，然后将差数组执行Divide方法即可
1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
int[] arr = {7,9,2,11,6,4,15,3,8}; //2 -7 9 -5 -2 11 -12 5
int[] arrs = new int[arr.length-1];
for (int i = 0; i < arrs.length; i++) {
arrs[i] = arr[i+1] - arr[i]; //arrs[2, -7, 9, -5 ,-2, 11, -12, 5]
}
int max = Divide(arrs,0,arrs.length-1);
System.out.println(max); //13
}
参考文章：分治法解决最大子数组问题
