注:看不懂评论区提问,有问必答。
问题:给定K个整数组成的序列{ N1, N2, ..., NK },“连续子列”被定义为{ Ni, Ni+1, ..., Nj },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2,1,-3,4,-1,2,1,-5,4},其连续子列{ 4,-1,2,1 }有最大的和6。
输入:数组个数k,整数数组a[MAXN],整数之间空格隔开。
输出:最大子序和maxsum。
一、双重循环:
T(n)=O(n2)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000 //数组最大空间
int main()
{
int k,i;
int a[MAXN]={0};
scanf("%d",&k);
for(i=0;i<k;i++)
scanf("%d",&a[i]);
printf("%d",Maxsub(a,k));
return 0;
}
int Maxsub(int A[],int N)
{
int thissum,maxsum=A[0];
int i,j;
for(i=0;i<N;i++)//从第一项开始遍历,i为子列左端部分
{
thissum=0;//每一回合置0
for(j=i;j<N;j++)//j为子列右端部分,A[i]到A[j]为子列
{
thissum+=A[j];
if(thissum>maxsum)//取最大值
maxsum=thissum;
}
}
return maxsum;
}
leetcode试题测试
![](https://img-blog.csdnimg.cn/20210915170802491.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAd2VpeGluXzQ1NzM0NDcz,size_20,color_FFFFFF,t_70,g_se,x_16)
二、分治法
从中间分开,利用子程序递归分别解决左半部分和右半部分最大子序列和,最后解决整体的最大子序列和。
T(n)=T(n/2)+T(n/2)+O(n)=O(nlogn)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000 //数组最大空间
int main()
{
int k,i;
int a[MAXN]={0};
scanf("%d",&k);
for(i=0;i<k;i++)
scanf("%d",&a[i]);
printf("%d",Maxsub(a,k));
return 0;
}
/*统一接口*/
int Maxsub(int list[],int N)
{
return Divide(list,0,N-1);
}
/*分治函数*/
int Divide(int list[],int left,int right)
{
int maxleftsum,maxrightsum;
int maxleftbordersum,maxrightbordersum;
int leftbordersum,rightbordersum;
int center,i;
/*递归终止条件,子列只有一个数字*/
if(left==right)
{
return list[left];
}
/*分治*/
center=(left+right)/2;
maxleftsum=Divide(list,left,center);
maxrightsum=Divide(list,center+1,right);
/*跨分界线最大子序和*/
maxleftbordersum=list[center];
leftbordersum=0;
for(i=center;i>=left;i--)
{
leftbordersum+=list[i];
if(leftbordersum>maxleftbordersum)
maxleftbordersum=leftbordersum;
}//左边结束
maxrightbordersum=list[center+1];
rightbordersum=0;
for(i=center+1;i<=right;i++)
{
rightbordersum+=list[i];
if(rightbordersum>maxrightbordersum)
maxrightbordersum=rightbordersum;
}//右边结束
/*返回分治结果*/
return Max3(maxleftsum,maxrightsum,maxleftbordersum+maxrightbordersum);
}
int Max3(int A,int B,int C)//三者求最大
{
return (A>B)?(A>C?A:C):(B>C?B:C);
}
LeetCode试题测试
![](https://img-blog.csdnimg.cn/20210915172907102.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAd2VpeGluXzQ1NzM0NDcz,size_20,color_FFFFFF,t_70,g_se,x_16)
三、在线处理(目前最优算法)
子序列和出现负数时,提前归零。每输入一个数据及时处理。
遍历一遍数组,所以T(n)=O(n)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000 //数组最大空间
int main()
{
int k,i;
int a[MAXN]={0};
scanf("%d",&k);
for(i=0;i<k;i++)
scanf("%d",&a[i]);
printf("%d",Maxsub(a,k));
return 0;
}
int Maxsub(int A[],int N)
{
int thissum,maxsum,i;
thissum=0;
maxsum=A[0];
for(i=0;i<N;i++)
{
thissum+=A[i];
if(thissum>maxsum)
maxsum=thissum;/*更新最大值*/
else if(thissum<0)/*子序列和为负*/
thissum=0;/*置0*/
}
return maxsum;
}
LeetCode试题测试
![](https://img-blog.csdnimg.cn/20210915183630271.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAd2VpeGluXzQ1NzM0NDcz,size_20,color_FFFFFF,t_70,g_se,x_16)
注:有一部分来自网页借鉴,不喜勿碰。