## 浙江大学MooC数据结构OJ——复杂度 原

fchen24

### 复杂度1 最大子列和问题

• 数据1：与样例等价，测试基本正确性；

• 数据2：102个随机整数；

• 数据3：103个随机整数；

• 数据4：104个随机整数；

• 数据5：105个随机整数；

``````6
-2 11 -4 13 -5 -2``````

``20``

CODE：

``````#include <stdio.h>
#define LEN 100000

int maxSubSeqSum( int a[], int n );
void printR( int result );

int main()
{
int n;
scanf("%d",&n);
int a[LEN];
int i;
for( i=0; i<n; i++ ){
scanf("%d",&a[i]);
}
printR(maxSubSeqSum( a, n ));
return 0;
}

int maxSubSeqSum( int a[], int n )
{
int ret=0;
int thisSum=0;
int i;
for( i=0; i<n; i++ ){
thisSum+=a[i];
if( thisSum>=ret ){
ret=thisSum;
}else if( thisSum<0 ){
thisSum=0;
}
}
return ret;
}

void printR( int result )
{
if( result ){
printf("%d\n",result);
}else{
printf("0\n");
}
}``````

### 复杂度2 Maximum Subsequence Sum

Given a sequence of KKK integers { N1N_1N1, N2N_2N2, ..., NKN_KNK }. A continuous subsequence is defined to be { NiN_iNi, Ni+1N_{i+1}Ni+1, ..., NjN_jNj } where 1≤i≤j≤K1 \le i \le j \le K1ijK. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer KKK (≤10000\le 1000010000). The second line contains KKK numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices iii and jjj (as shown by the sample case). If all the KKK numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

``````10
-10 1 2 3 4 -5 -23 3 7 -21``````

Sample Output:

``10 1 4  ``

CODE：

``````#include <stdio.h>

#define LEN 100000

int left,right;
int maxSubSeqSum( int a[], int n );
void printR( int result );

int main()
{
int n;
scanf("%d",&n);
int a[LEN];
int i;
for( i=0; i<n; i++ ){
scanf("%d",&a[i]);
}
left=a[0];
right=a[n-1];
printR(maxSubSeqSum( a, n ));
return 0;
}

int maxSubSeqSum( int *a, int n )
{
int ret=0;
int thisSum=0;
int i;
int ltemp,rtemp;
int flag=1;
for( i=0; i<n; i++ ){
thisSum+=a[i];
if( thisSum>ret ){
ret=thisSum;
right=a[i];
ltemp=left;
rtemp=right;
}else if( thisSum==0&&ret==0 ){
right=a[i];
ltemp=left;
rtemp=right;
flag=0;
}else if( thisSum<0 ){
thisSum=0;
left=a[i+1];
}
}
if( ret==0&&flag ){
left=a[0];
right=a[n-1];
}else if(ret!=0||!flag){
left=ltemp;
right=rtemp;
}
return ret;
}

void printR( int result )
{
if( result ){
printf("%d ",result);
}else{
printf("0 ");
}
printf("%d ",left);
printf("%d\n",right);
}``````

### fchen24

PTA 中国大学MOOC-陈越、何钦铭-数据结构 01-复杂度1 最大子列和问题（20 分） 给定K个整数组成的序列{ N1 , N2 , ..., Nk}，“连续子列”被定义为{ Ni , Ni+1 , ..., Nj}，其中 1≤i≤j≤K...

fesoncn
2017/10/28
0
0

Hosee
2015/10/23
2.6K
0
STL中的向量：vector

2017/11/17
0
0
Docker Meetup

1. 孙宏亮（DaoCloud)：深入分析Docker Container内部进程 讲师介绍： 孙宏亮，DaoCloud初创团队成员，软件工程师，浙江大学VLIS实验室应届研究生。读研期间活跃在PaaS和Docker开源社区，对C...

DaoCloud
2015/03/03
2.1K
11
Docker Meetup

1. 孙宏亮（DaoCloud)：深入分析Docker Container内部进程 讲师介绍： 孙宏亮，DaoCloud初创团队成员，软件工程师，浙江大学VLIS实验室应届研究生。读研期间活跃在PaaS和Docker开源社区，对C...

DaoCloud
2015/03/03
9
0

006-Docker中导出单个或多个tar包

docker中导出单个镜像和多个镜像的tar包 docker save [images] > [name.tar] docker save [images] [images] > [name.tar]...

6
0
Kotlin基础语法学习

T型人才追梦者

4
0
java实现简单计算器

1.概述 之前作者写过一篇文章,也是关于计算器的,用的是C++与Qt,链接在这里 这次用java的swing写的(这差距好像有点大,好吧是qt太强了). 先上图: 2.UI 总体布局使用流布局. (1)文本框 文本框就...

Blueeeeeee

4
0

6
0
OSChina 周二乱弹 —— 给我来个女菩萨

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @这次装个文艺青年吧 ：#今日歌曲推荐#分享XXXTENTACION/Travis Barker的单曲《Pain = BESTFRIEND》: 《Pain = BESTFRIEND》- XXXTENTACION/...

12
0