题目：

输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。

 

1.

1 /* 2     算法一：穷举法（3个for） 3             时间复杂度：O(n^3) 4  5 */ 6 #include 
     
       7 #include 
      
        8  9 int Max = 0;10 int find_max(int len, int arr[]){11     int i, j, k, sum;12     for(i=0; i
       
         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
       
      
     

2.

 

1 /* 2     算法二：算法一的优化 （2个for） 3             时间复杂度：O(n^2) 4 */ 5 #include 
     
       6 #include 
      
        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
       
         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
       
      
     

 将代码进行以下修改，可以得到该最大子序列和的开始元素和结束元素（low，high）

1 int find_max(int len, int arr[]){ 2     int i, j, sum, low, high; 3     for(i=0; i
     
       Max){ 8                 Max = sum; 9                 low = i;10                 high = j;11             }12         }13     }14     printf("The low is :%d\nThe high is : %d\n",arr[low],arr[high]);15     return Max;16 }
     

 

 

3.

1 /* 2     算法三：联机算法 3     时间复杂度：O(n) 4 */ 5 #include 
     
       6 #include 
      
        7  8 int Max = 0; 9 int find_max(int len, int arr[])10 {11     int i, sum = 0;12     for(i=0; i
       
         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
       
      
     

对以上代码进行小的改动，通过生成一系列的随机数进行测试程序运行的时间，由于程序运行的很快，需要通过重复循环取平均值的方法得到程序执行一次的时间。参考：http://www.cnblogs.com/LinSL/p/7475001.html

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          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
         
           max){35             max = sum;36         }else if(sum < 0){37             sum = 0;38         }39     }40     printf("The max_sum is:%d\n",max);41 }
         
        
       
      
     

 

参考：http://blog.163.com/kevinlee_2010/blog/static/169820820201010495438247/