c 最大子序列和_[OJ_Notes]最大子序列和的

叁歲伎倆 2023-01-10 10:09 114阅读 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

## 输出样例 ##

程序代码

#includeusing namespace std;void MaxSeqArraySum(int A[],int N);int main(){
             int n;//要输入的数字    cin>>n;    int *A = (int *)malloc(sizeof(int)*n);    for(int i=0;i    {
                 cin>>A[i];    }    MaxSeqArraySum(A,n);    return 0;    }void MaxSeqArraySum(int A[],int N){
             int thisSum,maxSum;    thisSum=maxSum=0;    for(int i=0;i    {
                 thisSum+=A[i];        if(thisSum>maxSum)            maxSum=thisSum;        else if(thisSum<0)            thisSum=0;    }    cout<endl;}

运行结果

![5004ef5cd82040edbf276f52ad641049.png][]

我的笔记

\[一本正经叨逼叨\] 今天听了陈越老师的课，本着温习的目的去PTA上面把相关的题目刷完了。以前的Notes都是用Markdown写的，但是涉及到图片，用Markdown写的文档在本地保存难免有隐患，且编辑之后用pdf的方式保存不利于检索，OneNote的Gem插件使用到期了，以后不能再OneNote里面写Markdown了，伤心。OneNote一贯继承了Office家族格式贼丑的特点，且不支持代码高亮，遂弃之。陈越老师讲的课很好，以前同学推荐了王卓老师的网课，但是听了几个小时发现过于基础且偏重于实操，而陈越老师的课会偏重于去讲算法的思想，听起来很舒服。 \[正文\] 本题所使用的算法是“在线处理算法”，使得求解”最大子序列的和“的算法的复杂度尽可能的小不是一个很简单的问题，常规的笨办法的算法的复杂度是N的立方量级，但是“在线处理算法”的算法复杂度是N，已经算是此问题算法复杂度的天花板了。在线处理算法中的“在线”意思是即时处理，在处理数字序列的过程中，程序在任何地方终止都会得到该位置的正确解答(分治法不能达到此目的),所以说是“在线处理算法”。 下面来描述一下“在线处理算法”的算法步骤，有数字序列\[-2, 11, -4, 13, -5, -2\],程序读入数字序列后进行处理，thisSum和maxSum初始化为0 1. i从0开始进入循环，thisSum执行加法运算后值为-2，此时thisSum<0，执行thisSum=0的赋值操作，进入下一个循环。 2. i=1进入下一个循环，循环开始之前thisSum==0，进入循环后thisSum=11，此时thisSum>maxSum=0，所以更新maxSum=11，thisSum=11，进入下一轮循环。 3. i=2进入下一个循环，循环开始之前thisSum==11，maxSum==11，进入循环后thisSum=70,所以进入下一轮循环 依次类推，最后的maxSum的值是20，返回结果,Done!!! 关于此算法的复杂度是怎么得来的：for循环体共循环N次，且循环体内的操作量级全部为O(1)，所以算法的复杂度T(N)=O(N)。

[5004ef5cd82040edbf276f52ad641049.png]: /images/20221119/648f7cee368549a093ed91fc133e03db.png