文档章节

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

fchen24
 fchen24
发布于 2016/04/18 19:00
字数 833
阅读 34
收藏 0

复杂度1 最大子列和问题 

给定KKK个整数组成的序列{ N1N_1N1, N2N_2N2, ..., NKN_KNK },“连续子列”被定义为{ NiN_iNi, Ni+1N_{i+1}Ni+1, ..., NjN_jNj },其中 1≤i≤j≤K1 \le i \le j \le K1ijK。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

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

  • 数据1:与样例等价,测试基本正确性;

  • 数据2:102个随机整数;

  • 数据3:103个随机整数;

  • 数据4:104个随机整数;

  • 数据5:105个随机整数;

输入格式:

输入第1行给出正整数KKK (≤100000\le 100000100000);第2行给出KKK个整数,其间以空格分隔。

输出格式:

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

输入样例:

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
粉丝 1
博文 8
码字总数 6620
作品 0
成都
私信 提问
数据结构学习笔记——最大子列和问题

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

fesoncn
2017/10/28
0
0
排序总结(不断更新)

排序法 最好时间分析 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n)(改进的冒泡排序) O(n2) O(n2) 稳定 O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 不稳定 O(log2n)~O(n) ...

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

关于 由于笔者原来一直使用的是python,所以想在c++中找到类似于python中的数据结构。后来发现用起来和python中的还是很像的。如果没有什么特殊要求或者复杂度问题,笔者建议在做OJ题目的时候...

AsuraDong
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基础语法学习

安装好安卓studio,以及插件支持Kotlin 就可以在创建项目的时候选择 Kotlin语言了。 https://www.jianshu.com/p/4ab13691d681 参考手册: https://www.runoob.com/kotlin/otlin-android-setu...

T型人才追梦者
今天
4
0
java实现简单计算器

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

Blueeeeeee
今天
4
0
纯CSS实现DIV悬浮(固定位置)

纯CSS实现的DIV悬浮效果(固定位置),兼容常用的浏览器:IE8、360、FireFox、Chrome、Safari、Opera、傲游、搜狗、世界之窗等。效果如下: 实现代码: <!DOCTYPE html> <html> <head> <meta ...

独钓渔
今天
6
0
OSChina 周二乱弹 —— 给我来个女菩萨

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

小小编辑
今天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部