PTA 最大子列和问题

女爷i 2024-02-19 16:13 29阅读 0赞

给定K个整数组成的序列\{ N1, N2, ..., NK \}，“连续子列”被定义为\{ Ni, Ni+1, ..., Nj \}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列\{ -2, 11, -4, 13, -5, -2 \}，其连续子列\{ 11, -4, 13 \}有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

*  数据1：与样例等价，测试基本正确性；
 *  数据2：102个随机整数；
 *  数据3：103个随机整数；
 *  数据4：104个随机整数；
 *  数据5：105个随机整数；

#### 输入格式: ####

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

#### 输出格式: ####

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

#### 输入样例: ####

6
    -2 11 -4 13 -5 -2

#### 输出样例: ####

陈越姥姥让把最大子列的起点、终点也找出来。

第二个算法的起点、终点还未想出怎么找，其余均已想好。

下面的算法带有起点和终点的输出（除了算法2）。

1.最容易想到的算法：

时间复杂度为o(n^2)

#include<stdio.h>
    #define size 100005
    int max_s=-1;
    int max_e=-1;
    int Max_Subseq2(int a[],int n)        //很简单的一种算法 ，时间复杂度为o(n^2) 
    {
    	int i,j,max_sum=0,this_sum=0;
    	for(i=0;i<n;i++)
    	{
    		this_sum=0;
    		for(j=i;j<n;j++)
    		{
    			this_sum+=a[j];
    			if(this_sum>max_sum)
    			{
    				max_sum=this_sum;
    				max_s=i;
    				max_e=j;
    			}
    			
    		}
    	}
    	return max_sum;
    }
    
    int main()
    {
    	int a[size];
    	int i,j,n;
    	while(~scanf("%d",&n))
    	{
    		for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    		printf("%d\n",Max_Subseq2(a,n));
    		printf("%d %d\n",max_s,max_e);
    	}
    	return 0;
     }

2.时间复杂度为o（nlog（n））

这个是看评论区仿写的，惭愧~

具体思路：

![a22dac90-f5eb-4a23-bc2b-9f9e41db9991.jpg_imageView][]

#include<stdio.h>
    #define size 100005
    int The_max_num(int a,int b,int c)     //求三个数的最大值，嵌套使用三目运算符 
    {
    	return a>b?(a>c?a:c):(b>c?b:c);
    }
    int Max_Subseq3(int num[],int left,int right)            //采用分而治之的算法思想，类似 二分查找 
    {
    	int i,mid=0;                                        // 把变量声明 定义在开头  是一种好习惯 
    	int max_left_sum=0,max_right_sum=0;
    	int this_left_border_sum=0,this_right_border_sum=0;
    	int max_left_border_sum=0,max_right_border_sum=0;
    	if(left==right)                                      //“分”到 每个子列的个数为1 
    	{
    		if(num[left]<=0)
    		return 0;
    		else
    		return num[left];
    	}               
    	mid=(left+right)/2;    
    	max_left_sum=Max_Subseq3(num,left,mid);             //对左、右半边找最大子列和   “分”的思想 
    	max_right_sum=Max_Subseq3(num,mid+1,right);
    	for(i=mid;i>=left;i--)                              //考虑 跨界的情况            “治”的思想 
    	{
    		this_left_border_sum+=num[i];
    		if(this_left_border_sum>max_left_border_sum)
    		max_left_border_sum=this_left_border_sum;
    	} 
    	for(i=mid+1;i<=right;i++)
    	{
    		this_right_border_sum+=num[i];
    		if(this_right_border_sum>max_right_border_sum)
    		max_right_border_sum=this_right_border_sum;
    	} 
    	return The_max_num(max_left_sum,max_right_sum,max_left_border_sum+max_right_border_sum);    //返回三者的最大值 
    }
    int main()
    {
    	int a[size];
    	int i,j,n;
    	while(~scanf("%d",&n))
    	{
    		for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    		printf("%d\n",Max_Subseq3(a,0,n));
    	}
    	return 0;
     }

#include<stdio.h>
    #define size 100005
    int max_s=-1;  // 设置全局变量：最大子列和的起点、终点 
    int max_e=-1; 
    int Max_Subseq4(int num[],int n)       //“在线处理”，时间复杂度为0（n） 
    {
    	int max_sum=0;
    	int i=0;
    	int this_sum=0;
    	for(i=0;i<n;i++)              //是一种动态规划 
    	{
    		this_sum+=num[i];
    		
    		if(this_sum>max_sum)
    		{
    			max_sum=this_sum;
    			max_e=i;               //记下终点 
    		}
    		else
    		if(this_sum<0)           //如果前面的和小于零，只能减小子列和，不能增大子列和，故忽略前面的和。 
    		{
    			this_sum=0;
    			max_s=i+1;            //起点往后推 
    		}
    	}
    	return max_sum;
    }
    int main()    
    {
    	int a[size];
    	int i,j,n;
    	while(~scanf("%d",&n))
    	{
    		for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    	
    		printf("%d\n",Max_Subseq4(a,n));
    		printf("%d %d\n",max_s,max_e);
    	}
    	return 0;
     }

时间复杂度为o(n)

采用动态规划的思想。

[a22dac90-f5eb-4a23-bc2b-9f9e41db9991.jpg_imageView]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/43cba12ff2dd4145b0814710d1605abc.png