求一个序列的子序列的最大值，这是一个经典算法，这里稍作整理。
问题：任给一个整数序列，如{-2, 5, 7, 11, -4, 13, -5, -2, -6, 3, -1, 3}，求出这个序列中连续子序列的和的最大值，这个例子中最大值为32，子序列为{5, 7, 11, -4, 13}。
方法一：最简单的暴力法。确立一个起点，一个终点，计算起点到终点的和。下面代码中int brute_force(int* a,int n)实现了该算法，时间复杂度由
计算可得为O(n^3)。
方法二：对暴力法的优化，使用累加的方法，确定一个起点之后，将前面序列的和累加到终点，选取一个最大值。下面代码中int improved_brute_force(int* a, int n)，实现了该算法。时间复杂度由
可得为O(n^2)。
方法三：采用分治法的思想，从中间点将序列分成两个子序列，整个序列的最大子序列位置分三种情况（见图，此图来自老师PPT）1.在左侧子序列中2.在右侧子序列中3.包含中间点，两个序列各有一部分。
下面的int divide_conquer(int* a,int start,int end)方法实现了该算法，，该递归实现的递归式为T(n)=2T(n/2)+cn。由Master theorem可得时间复杂度为O(nlogn).
方法四：采用动态规划的思想，又称为Online algorithm，在线学习算法的定义：线上算法是一种处理输入资料的独特形式，算法开始的时候不需要所有的数据都准备好，而是对逐步输入的数据进行处理，并在输入完成之后输出运算结果。与之相对的是离线算法，假设所有数据在算法开始时都已经准备好，选择排序是离线算法，插入排序是在线算法。用动态规划处理最大子序列长度的思想为用变量max_value保存最大子序列的和，用current_value保存从i=0累加的的和，如果current_value大于max_value则保存，否则放弃，如果current减小到零，则将current_value从0重新开始计因为再讲current_value累加的话只会减少子序列的和。下面的int dynamic_prom(int* a,int len)实现了该算法。该算法时间复杂度为O(n)
#include <stdio.h>#include <stdlib.h>#include <limits.h>#define len_array 12/*求最大子序列的和*///brute force：时间复杂度n^3int brute_force(int* a,int n){ int i,j,k;int max_value = INT_MIN;int current_value;for(i=0;i<n;i++){//以i为起点for(j=i;j<n;j++){//以j为终点current_value = 0;for(k=i;k<=j;k++){//求从i到j的子序列的和current_value += a[k];}if(current_value > max_value){max_value = current_value;}}}return max_value;}//提高的brute force, 时间复杂度n^2int improved_brute_force(int* a, int n){int i,j;int max_value = INT_MIN;int current_value = 0;for(i=0;i<n;i++){//以i为起点current_value = 0;//设置以i为起点的子序列的初始值为0for(j=i;j<n;j++){//以j为终点current_value += a[j];if(current_value>max_value){max_value = current_value;}}}return max_value;}//分治法，时间复杂度nlog(n)//从中间点将序列分成两个子序列，整个序列的最大子序列位置分三种情况//1.在左侧子序列中//2.在右侧子序列中//3.包含中间点，两个序列各有一部分int divide_conquer(int* a,int start,int end){int mid;int mid_to_left_max = 0;int mid_to_right_max = 0;int i,current_left=0,current_right=0;int side_max,mid_max,max,left_max,right_max;if(start==end)return a[start];mid = (start+end)/2;left_max = divide_conquer(a,start,mid);//寻找左侧子序列的最大值right_max = divide_conquer(a,mid+1,end);//寻找右侧子序列的最大值for(i=mid;i>=0;i–){//寻找以中间点为起点，向左延伸的最大子序列current_left += a[i];if(current_left>mid_to_left_max){mid_to_left_max = current_left;}}for(i=mid;i<=end;i++){//寻找以中间点为起点，向右延伸的最大子序列current_right += a[i];if(current_right>mid_to_right_max){mid_to_right_max = current_right;}}mid_max = mid_to_left_max+mid_to_right_max-a[mid];side_max = left_max>right_max?left_max:right_max;max = side_max>mid_max?side_max:mid_max;return max;}//又称为Online algorithm，在线学习算法的定义：线上算法是一种处理输入资料的独特形式，算法开始的时候//不需要所有的数据都准备好，而是对逐步输入的数据进行处理，并在输入完成之后输出运算结果。与之相对的是//离线算法，假设所有数据在算法开始时都已经准备好，选择排序是离线算法，插入排序是在线算法//用动态规划处理最大子序列长度的思想为用变量max_value保存最大子序列的和，用current_value保存从i=0累加的//的和，如果current_value大于max_value则保存，否则放弃，如果current减小到零，则将current_value从0重新开始计//因为再讲current_value累加的话只会减少子序列的和int dynamic_prom(int* a,int len){int current_value = 0;int max_value = INT_MIN;int i;for(i=0;i<len;i++){current_value += a[i];if(current_value>max_value){//当前值大于最大值，更新max_value = current_value;}if(current_value<0){//当前值小于零，从0开始current_value = 0;}}return max_value;}int main(){int a[12] = {-2, 5, 7, 11, -4, 13, -5, -2, -6, 3, -1, 3};printf("brute force: %d\n",brute_force(a,len_array));printf("improved brute force: %d\n",improved_brute_force(a,len_array));printf("divide conquer: %d\n",divide_conquer(a,0,len_array-1));printf("dynamic programming: %d\n",dynamic_prom(a,len_array));printf("\n");return EXIT_SUCCESS;}
只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。
