问题一
最大连续子数组
问题描述：
给定一个数组A[0,…,n-1]，求A的连续子数组，使得该子数组的和最大
问题举例：
数组：1，-2，3，10，-4，7，2，-5
最大子数组：3，10，-4，7，2
思路分析：
1、暴力法 2、分治法 3、分析法 4、动态规划法
问题解决：
1、该问题使用暴力法进行解决的思路比较简单，就是将整个数组的所有结果进行计算并比较就能得到最大子数组。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class BiggestSumFromSubArray {
private int maxSubArray(int[] a){
int maxSum = a[0];
int curSum;
for(int i=0;i<a.length;i++){
for (int j=i;j<a.length;j++){
curSum = 0;
for(int k=i;k<=j;k++){
curSum += a[k];
}
if(curSum > maxSum)
maxSum = curSum;
}
}
return maxSum;
}
public static void main(String[] args) {
BiggestSumFromSubArray bsfs = new BiggestSumFromSubArray();
int[] a = {1,-2,3,10,-4,7,2,-5};
System.out.println(bsfs.maxSubArray(a));
}
}
分析：
可以看到代码中使用了三层for循环，第一层for循环自然是将整个数组包含进去，第二层的变量j以第一层的i为起点，这样是为了保证不会漏掉结果，比如i=0时，第二层循环就能保证产生从0下标开始的所有结果(比如0，0+1，0+1+2…)，第三层循环是为了在第二层的基础上进行内部比较，比如i=0，j=2时，由于k=i，则k=0，k<=2，在这个基础上可以计算a[0]+a[1]+a[2]的值，由于最开始已经将maxSum的值设定为了a[0]，所以这其实就是比较a[0]+…+a[7]中所有结果的最大值，然后进入第二次的循环，此时i=1开始，计算所有a[1]+…+a[7]的所有可能结果，最终就能计算出最大的子数组，此方法时间复杂度较大，达到了O(n3)，不适用于较大规模的运算。
2、分治法的思想是将待处理的数据进行分组，从而降低计算的复杂度，我们可以将数组以中点为分割点，从而得到左右两个子数组，此时最大的子数组可能位于左边数组、右边数组或者跨左右两个数组，而我们可以分别对这三种情况进行求解，比较得到最大值。
代码：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
46public class BiggestSumFromSubArray_DCVer {
/**
*
* @param a 待使用数组
* @param from 子数组的起始下标
* @param to 子数组的结尾下标
* @return 最大子数组的和
*/
private int maxAddSub(int[] a, int from, int to){
if(to==from)
return a[from];
int middle = (from+to)/2;
int m1 = maxAddSub(a,from,middle);
int m2 = maxAddSub(a,middle+1,to);
int i;
int left = a[middle],now = a[middle];
for(i = middle-1;i>=from;--i){
now += a[i];
left = max(now,left);
}
int right = a[middle+1];
now = a[middle+1];
for(i = middle+2;i<=to;++i){
now +=a[i];
right = max(now,right);
}
int m3 = left+right;
return max(m1,m2,m3);
}
private int max(int a, int b){
return a>b?a:b;
}
private int max(int a, int b, int c){
int bothMax = a>b?a:b;
return c>bothMax?c:bothMax;
}
public static void main(String[] args) {
BiggestSumFromSubArray_DCVer bsfs_dc = new BiggestSumFromSubArray_DCVer();
int a[] = {1,-2,3,10,-4,7,2,-5};
System.out.println(bsfs_dc.maxAddSub(a,0,a.length-1));
}
}
分析：
从代码中可以看出，m1、m2和m3分别代表了之前提到的左边数组、右边数组和跨数组的情况，以示例中的数组1、-2、3、10、-4、7、2、-5为例进行说明。maxAddSub这个函数一开始就判断首尾有没有重合，若重合则代表没有可相加元素，自然就返回当前的值，然后计算middle值，这是为了进一步缩小范围，第一次计算middle的值为(0+7)/2向下取整为3，则代表接下来的操作都是处理1、-2、3、10这个小数组，然后重复上述过程，最终得到to==from=0这个情况，则返回0下标的值为1，则此时m1的值为1，然后对m2进行计算，第一次计算时middle+1和to的值都是1，则返回a[1]，即m2=-2。计算完m1和m2的值之后就开始计算跨数组的值，这个值的计算方法就是以middle为界，left就从middle开始，逐步下标递减进行相加，找出最大值，right就从middle+1开始，逐步下标递增进行相加，找到最大值，这样能保证跨数组时值是连续的，而不是直接将左右两个数组的最大值相加。这样就能计算出m3的值，最后将m1、m2和m3的值进行比较得出一轮后的最大值。比如第一轮过后m1=1，m2=-2，m3=-1，此时三者最大值自然是1，然后该值被返回，此处要搞清楚一个重要问题，那就是这个1被返回给了哪一层，以及其返回之后的上层数据是什么样子，这是理解递归的重要一步。通过执行顺序我们可以得知maxAddSub函数的值都被返回给了m1，其实我们在第一次进入m1=maxAddSub(a,from,middle)这层递归后就一直被困在内部，所以要记住第一次进入该递归时from=0，middle==to=3(当然，最外层的这个maxAddSub的from是0，to是7)，所以此时就能明白m1的值为比较完m1、m2和m3的最大值，也就是m1=1，然后进入的这个m2就是从middle+1也就是2到to也就是middle的值为3，继续上述比较。
分治法的时间复杂度是O(nlogn)。
3、我们使用分析法首先对问题进行分析，既然是要求最大子数组，那么我们可以先求前缀和，比如a[0]+a[1]+…+a[n-1]，从中统计出最大的子数组，然后记录取得这个最大值时的最后一个下标k，在第二次循环中找出0-k这个范围内的最小值，这个最小值必须小于0，如果不小于0就最后返回0，如果小于0则将其减掉，这样就能得出最大的子数组。
代码：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
29public class BiggestSumFromSubArray_MathVer {
private int maxAddSub(int[] a){
int max = a[0];
int min = 0;
int maxTemp = 0;
int minTemp = 0;
int index = 0;
for (int i=0;i<a.length;i++){
maxTemp+=a[i];
if(maxTemp>max){
max = maxTemp;
index = i;
}
}
for (int i=0;i<index;i++){
minTemp += a[i];
if(minTemp<min){
min = minTemp;
}
}
return max-min;
}
public static void main(String[] args) {
BiggestSumFromSubArray_MathVer bsfs_mv = new BiggestSumFromSubArray_MathVer();
int a[] = {1,-2,3,10,-4,7,2,-5};
System.out.println(bsfs_mv.maxAddSub(a));
}
}
分析：
此代码比较简单，基本上就是对上述思路的一个代码表达，并且只使用了两次遍历，导致其时间复杂度仅为O(n)，达到了线性级别，可以说其效率的提升非常明显。
4、动态规划的思想非常的清晰，就是走一步看一步，根据之前得到的结果不断调整策略，在此问题中，我们先设result和sum是a[0]，然后逐步相加，如果发现sum>0，则代表后面的数对于求得最大值具有积极影响，则加上，否则代表加上后面的数之后反而会使得目前的和变为负数，则跳过此结果，将sum的值置为新的值，重复上述过程。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class BiggestSumFromSubArray_DPVer {
private int maxSubArray(int[] a){
int result = a[0];
int sum = a[0];
for(int i=1;i<a.length;i++){
if(sum>0)
sum+=a[i];
else
sum = a[i];
if(sum>result)
result = sum;
}
return result;
}
public static void main(String[] args) {
BiggestSumFromSubArray_DPVer bsfs_dpv = new BiggestSumFromSubArray_DPVer();
int[] a = {1,-2,3,10,-4,7,2,-5};
System.out.println(bsfs_dpv.maxSubArray(a));
}
}
分析：
这段代码也比较简单，只需要注意循环时的舍弃问题，当发现上一次相加之后sum为负值则在本次循环时重新赋值，由于本方法只需要一次遍历，所以时间复杂度同样为O(n)。