最大子列和

给定N个整数的序列{A1,A2,A3,……}

求最大的子列和：所谓最大子列和就是这个序列中一块连续的序列的和

1. 算法一：暴力算法

暴力算法，按照题意，循环两次表示首尾，算两个中间的和

int max_subseq_sum(int A[], int N)
{
    int sum, max_sum;
    int i j, k;
    
    for(i = 0; i < N; i++)
    {  
    	for(j = i; j < N; j++)
      	{
            sum = 0;
        	for(k = i; k <= j; k++)
          	{
            	sum += A[k];
          	}
      		if(sum > max_sum)
                max_sum = sum;
      	}
    }
    return max_sum;
}

这个算法的时间复杂度是O(n^3)

2. 算法二：动点脑子的暴力算法

算从每个i开始的最大子列和

int max_subseq_sum(int A[],int N)
{
    int sum, max_sum = 0;
    int i, j;
    for(i = 0;i < N;i++)
    {
        sum = 0;
        for(j = i;j < N; j++)
        {
            sum += A[j];
            if(sum>max_sum)
                max_sum = sum;
        }
    }
    return max_sum；
}

时间复杂度是O(n^2)

O(n^2) 一般可以转换成O(nlogn)的复杂度

3. 算法三 分治法

将序列一分为2

然后分别找出左右两边的最大子列和

然后找出跨越边界的最大子列和

在找左右的最大子列和的时候可以继续使用分治法

分治完之后就要和，就是那个跨越边界的问题

T(N) = 2T(N/2) + O(N) //整个是T(N),那么分治之后就是T(N/2)，然后合并的时候跨越边界需要一次遍历就是O(N)
	 = 2(2T(N/4)+O(N/2))+O(N)
	 = ……
     = 2^k T(1) + kO(N)	//
N/(2^k) = 1

可以计算得到时间复杂度是O(nlogn)

int max3(int a, int b, int c)
{
	return A>B?A>C?A:C:B>C?B:C;
}
int divide_and_conqur(int list[], int left, int right)
{
    int max_left_sum,max_right_sum;		//左侧和，右侧和
    int max_left_border_sum, max_right_border_sum;	//左侧最大和，右侧最大和
    int left_border_sum, right_border_sum;//左侧边缘数字，靠近中间的，右边靠近中间的数字的和
    int center ,i;
    
   	if(left == right)	//左边==右边，分治到只剩一个数字了，到头了
    {
        if(list[left] > 0)	//大于0就返回，否则就是一个数字都没有最大
            return list[left];		//左右合一了，返回左边或者右边区别不大
        else
            return 0;
    }
    
    cneter = (left + right)/2;
    max_left_sum = divide_and_conqur(list, left, center);		//递归分
    max_rignt_sum = divide_and_conqur(list,center+1,right);
    
    max_left_border_sum = 0;	//
    left_border_sum = 0;
    for(i=center; i>= left; i--)	//从靠近中间开始找，找到最边缘开始的最大值
    {
        left_border_sum += list[i];
        if(left_border_sum > max_left_border_sum)
            max_left_border_sum = left_border_sum;
    }
    max_right_border_sum = 0;
    right_border_sum = 0;
    for(i=center+1; i<= right; i++)
    {
        right_border_sum += list[i];
        if(right_border_sum > max_right_border_sum)
            max_right_border_sum = right_border_sum;
    }
    
    return max3(max_left_sum,max_right_sum, max_left_border_sum + max_right_border_sum);
    //最大值必然产生于左边最大值、右边最大值，或者两个边缘的最大值的和
}

int max_subseq_sum(int list[], int N)
{
    return divide_and_conqur(list, 0, N-1);
}

4. 算法四：在线处理算法

int max_subseq_sum(int A[], int N)
{
	int sum, max_sum = 0;
	int i;
	sum = max_sum = 0;
	for(i=0; i<N; i++)
	{	
		sum += A[i];
		if(sum>max_sum)
			max_sum = sum;
		else if(sum<0)
			sum = o;	//负数不可能使下面的和要大，所以抛弃它
	}
	return max_sum;
}

这个算法的时间复杂度是O(n)

这个算法很妙哇