C_求最大连续子序列和

 1 /*
 2     算法一：穷举法（3个for）
 3             时间复杂度：O(n^3)
 4 
 5 */
 6 #include <stdio.h>
 7 #include <malloc.h>
 8 
 9 int Max = 0;
10 int find_max(int len, int arr[]){
11     int i, j, k, sum;
12     for(i=0; i<len; i++){
13         for(j=i; j<len; j++){
14             sum = 0;
15             for(k=i; k<=j; k++){
16                 sum += arr[k];
17             }
18             if(sum > Max){
19                 Max = sum;
20             }
21         }
22     }
23     return Max;
24 
25 } 
26 
27 int main(){
28     int i, len, *arr;
29     printf("请输入数组的长度： ");
30     scanf("%d",&len);
31     arr = (int *)malloc(sizeof(int)*len);
32     printf("请输入数组的值：");
33     for(i=0; i<len; i++){
34         scanf("%d",&arr[i]);
35     }
36     find_max(len,arr);
37     printf("最大连续子序列和 :%dn", Max );
38     
39     return 0;
40 }

 1 /*
 2     算法二：算法一的优化 （2个for）
 3             时间复杂度：O(n^2)
 4 */
 5 #include <stdio.h>
 6 #include <malloc.h>
 7 
 8 int Max = 0;
 9 int find_max(int arr[],int n, int len){
10       int i, sum = 0;
11     for(i=n; i<len; i++){
12         sum += arr[i];
13         if(sum > Max){
14             Max = sum ;    
15         }
16     }
17     return Max;
18 } 
19 
20 int main(){
21     int i, len,  *arr;
22     printf("请输入数组的长度：");
23     scanf("%d",&len);
24     arr = (int *)malloc(sizeof(int)*len);
25     printf("请输入数组的值：");
26     for (i=0; i<len; i++)
27     {
28         scanf("%d", &arr[i]);
29     }
30 
31     
32     for(i=0; i<10; i++){
33        find_max(arr,i, len);
34     }
35         
36     printf("最大连续子序列和：%d n",Max);
37 
38     return 0;
39 }

 1 int find_max(int len, int arr[]){
 2     int i, j, sum, low, high;
 3     for(i=0; i<len; i++){
 4         sum = 0;
 5         for(j=i; j<len; j++){
 6             sum += arr[j];
 7             if(sum > Max){
 8                 Max = sum;
 9                 low = i;
10                 high = j;
11             }
12         }
13     }
14     printf("The low is :%dnThe high is : %dn",arr[low],arr[high]);
15     return Max;
16 }

 1 /*
 2     算法三：联机算法
 3     时间复杂度：O(n)
 4 */
 5 #include <stdio.h>
 6 #include <malloc.h>
 7 
 8 int Max = 0;
 9 int find_max(int len, int arr[])
10 {
11     int i, sum = 0;
12     for(i=0; i<len; i++)
13     {
14         sum += arr[i];
15         if(sum  > Max)
16         {
17             Max = sum;
18         }else if(sum < 0){
19             sum = 0;
20         }    
21     }
22 
23     return Max;
24 }
25 
26 int main(){
27     int i, len, *arr;
28     printf("请输入数组的长度：");
29     scanf("%d",&len);
30     arr = (int *)malloc(sizeof(int)*len);
31     printf("请输入数组的值：");
32     for (i=0; i<len; i++)
33     {
34         scanf("%d", &arr[i]);
35     }
36     find_max(len, arr);
37     printf("最大连续子序列和：%d n",Max);
38     return 0;
39 }

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <malloc.h>
 4 #include <time.h>
 5 
 6 clock_t start,stop;
 7 double duration;
 8 
 9 void fun(int len,int arr[]);
10 
11 int main(){
12     int len, *arr, i;
13     printf("Please enter the len:");
14     scanf("%d",&len);
15     arr = (int*)malloc(sizeof(int)*len);17     for(i=0; i<len; i++){
16         arr[i] = rand()%2001-1000;/*产生-1000~1000之间的随机数*/
17         printf("%d ",arr[i]);
18     }
19     printf("n");
20     start = clock();
21     fun(len,arr);
22     stop = clock();
23     duration = ((double)(stop - start))/CLK_TCK;
24     printf("The duration is:%fn",duration);/*0.0000*/
25     return 0;
26 }
27 
28 void fun(int len,int arr[]){
29     int max=0,
30         sum=0,
31         i;
32     for(i=0; i<len; i++){
33         sum += arr[i];
34         if(sum > max){
35             max = sum;
36         }else if(sum < 0){
37             sum = 0;
38         }
39     }
40     printf("The max_sum is:%dn",max);
41 }