Maximum Subsequence Sum最大子列和问题（c语言实现）

本是古典何须时尚 2021-11-17 08:04 187阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

### 代码 ###

#include <stdio.h>
    #define MaxSize 100000
    int main(){
    	int K;	
    	int i;
    	int a[MaxSize];
    	int flag=0,zero=0;
    	int ThisSum=0,MaxSum=0;
    	int tempindex=0;
    	scanf("%d",&K);			//输入数组长度K
    	int first=0,last=K-1;
    	for(i=0;i<K;i++){
    		scanf("%d",&a[i]);	//输入K个整数
    		if(a[i]>0) flag=1;	//有正整数
    		if(a[i]==0) zero=1;	//有0（一开始把==写成了=）
    	}
    	if(flag){
    		for(i=0;i<K;i++){
    			ThisSum+=a[i];
    			if(ThisSum>MaxSum){
    				MaxSum=ThisSum;
    				first=tempindex;
    				last=i;
    			}
    			if(ThisSum<0){
    				ThisSum=0;
    				tempindex=i+1;
    			}	
    		}
    		printf("%d %d %d\n",MaxSum,a[first],a[last]);
    	}else if(zero){
    		printf("0 0 0\n");
    	}else{
    		printf("0 %d %d\n",a[first],a[last]);
    	}
    	return 0;
    }

### 结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211116/ce519678199141e0abd4b7b4cf1a0eaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211116/e1c8aea81af644c597b713faef03d58c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子列和问题（Java语言实现）

最大子列和问题（Java语言实现） **一、问题描述**：给定N个整数的序列 \{ A 1 , A 2 , . . . , A n \} \\left \\\{ A\...

痛定思痛。/ 2024年04月17日 05:40/ 0 赞/ 31 阅读

相关 LeetCode:53. Maximum Subarray 最大子序和（C语言）

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: \[-2,1,-3,4,-1,2,1

今天药忘吃喽~/ 2023年06月30日 02:19/ 0 赞/ 57 阅读

相关最大子列和求解O(n)c语言

> 核心思想：如果整数序列\{a1, a2,…,an\}的最大子列和是\{ai, ai+1,…,aj\}，那必定有∑ai~al≥0对任意i≤l小于等于j成立。因此，一旦发现当前

布满荆棘的人生/ 2022年11月28日 13:54/ 0 赞/ 62 阅读

相关 Python 实现1007. Maximum Subsequence Sum (25)

1007. Maximum Subsequence Sum (25) Given a sequence of K integers \{ N1, N2, …, NK \}

待我称王封你为后i/ 2022年06月13日 03:18/ 0 赞/ 144 阅读

相关 PAT甲级1007. Maximum Subsequence Sum

Given a sequence of K integers \{ N1, N2, …, NK \}. A continuous subsequence is defined

桃扇骨/ 2022年06月11日 03:25/ 0 赞/ 137 阅读

相关 PAT甲级-1007. Maximum Subsequence Sum (25)最大子序列和

1007. Maximum Subsequence Sum (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000

太过爱你忘了你带给我的痛/ 2022年05月31日 09:39/ 0 赞/ 121 阅读

相关 1007. Maximum Subsequence Sum (25)

Given a sequence of K integers \{ N1, N2, ..., NK \}. A continuous subsequence is define

男娘i/ 2022年05月31日 07:05/ 0 赞/ 107 阅读

相关最大子列和问题

01-复杂度1 最大子列和问题（20 分）给定K个整数组成的序列\{ N1, N2, ..., NK \}，“连续子列”被定义为\{ Ni, N

浅浅的花香味﹌/ 2022年05月04日 02:26/ 0 赞/ 126 阅读

相关 (PAT 1007) Maximum Subsequence Sum (DP-最大字串)

Given a sequence of K integers \{ N1, N2, ..., NK \}. A continuous subsequence is define

男娘i/ 2022年03月19日 06:36/ 0 赞/ 92 阅读

相关 Maximum Subsequence Sum最大子列和问题（c语言实现）

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

本是古典何须时尚/ 2021年11月17日 08:04/ 0 赞/ 188 阅读