蛮力法、分治法、动态规划法解决实现最大子段和问题_什么问题可以同时用蛮力,变治,动态规划求解

首先使用蛮力法解决

int Max_Brute(int len,int a[]){
	int n = len;
    int max = 0;
	int i,j;
	for(i = 0;i<n;i++){
		for(j = i;j<n;j++){
			int k;
			int num = 0;
			for(k=i;k<=j;k++){
				num += a[k];
			} 
	
			if(num>max){
			    max = num;
		    }
		}
	}
	return max;	 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里使用了未经任何改良的蛮力法，效率低下但简洁明了。
其次使用动态规划法递归解决。

int Max_Divide(int a[],int left,int right){//left和right代表计算a[left]到a[right]
	int i,j;
	int sum = 0,midSum = 0,leftSum = 0,rightSum = 0;
	int center,s1,s2,lefts,rights;
	if(left == right){//如果只有一个值，则其为该片段最大值
		sum = a[left];
	}
	else{
		center = (left+right)/2;
		leftSum = Max_Divide(a,left,center);//计算第一种情况（左半部分）最大值
		rightSum = Max_Divide(a,center+1,right);//计算第二种情况（右半部分）最大值
		s1 = 0;
		lefts = 0;
		for( i = center;i>=left;i--){//计算s1
			lefts += a[i];
			if(lefts>s1){
				s1 = lefts;
			}
		}
		s2 = 0;
		rights = 0;
		for(j = center+1;j<=right;j++){//计算s2
			lefts += a[i];
			rights += a[j];
			if(rights>s2){
				s2 = rights;
			}
		}
		midSum = s1+s2;
		if(midSum<leftSum){
			sum = leftSum;
		}
		else{
			sum = midSum;
		}
		if(sum<rightSum){
			sum = rightSum;
		}
	}
	return sum;
}

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

动态规划法：

#define max(a,b) ( ((a)>(b)) ? (a):(b) )
int Max_Dynamic(int len,int a[]) {
    int res = 0;
    int b = 0;
    int i;
    for (i = 0; i < len; i++) {
        b = max(b + a[i], a[i]);
        if (b > res) 
			res = b;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

对三种算法进行测试

#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
	int a[] = {-20,11,-4,14,-5,-2};
	printf("%d,%d,%d",Max_Brute(6,a),Max_Divide(a,0,5),Max_Dynamic(5,a));

}
1
2
3
4
5
6
7
8

结果如下