01-复杂度1 最大子列和问题

约定不等于承诺〃 2022-08-10 08:54 53阅读 0赞

01-复杂度1 最大子列和问题

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

### 输入格式: ###

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

### 输出格式: ###

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

### 输入样例: ###

6
    -2 11 -4 13 -5 -2

### 输出样例: ###

20

#include<iostream>
    using namespace std;
    int main()
    {
    	int k;
    	scanf("%d", &k);
    	int *a = new int[k];
    	for (int i = 0; i < k; i++)
    		scanf("%d", &a[i]);
    	int first, last,sum=0,max=0,right,left=0;
    	for (int i = 0; i < k; i++)
    	{
    		sum += a[i];
    		right = i;
    		if (sum>max)
    		{
    			max = sum;
    			first = left;
    			last = right;
    		}
    		if (sum < 0)
    		{
    			sum = 0;
    			left = i + 1;
    		}
    	}
    	cout << max;
    /*	if (max == 0)
    		cout << " " << a[0] << " " << a[k-1];
    	else
    		cout << " " << first<< " " << last;
    	*/return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 PTA 最大子列和问题

给定K个整数组成的序列\{ N1, N2, ..., NK \}，“连续子列”被定义为\{ Ni, Ni+1, ..., Nj \}，其中 1≤i≤j≤K。“最大子列和”则被定

女爷i/ 2024年02月19日 16:13/ 0 赞/ 41 阅读

相关 01-复杂度1 最大子列和问题

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

约定不等于承诺〃/ 2022年08月10日 08:54/ 0 赞/ 54 阅读

相关子数列的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。从数组第一

男娘i/ 2022年08月05日 20:59/ 0 赞/ 155 阅读

相关 7-1 最大子列和问题

给定K个整数组成的序列\{ N1，N2 , ..., NK\}，“连续子列”被定义为\{ Ni , Ni+1, ..., Nj\}，其中 1≤i≤j≤K。“最大子列和”则被定义

小灰灰/ 2022年05月23日 09:37/ 0 赞/ 135 阅读

相关《数据结构》01-复杂度1 最大子列和问题

题目给定K个整数组成的序列\{ N 1 \_1 1, N 2 \_2 2, …, N k \_k k\}，“连续子列”被定义为\{ N i \_\{i\} i , N

向右看齐/ 2022年05月08日 07:06/ 0 赞/ 138 阅读

相关 7-1 最大子列和问题（20 分）

给定K个整数组成的序列\{ N1, N2, …, NK \}，“连续子列”被定义为\{ Ni, Ni+1, …, Nj \}，其中 1≤i≤j≤K。“最大子列和”则被定义为所有

灰太狼/ 2022年05月08日 02:26/ 0 赞/ 162 阅读

相关最大子列和问题

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

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

相关 7-1 最大子列和问题 (20 分)

7-1 最大子列和问题 (20 分) 给定K个整数组成的序列\{ N 1 , N 2 , …, N K \}，“连续子列”被

落日映苍穹つ/ 2022年02月04日 02:59/ 0 赞/ 177 阅读

相关最大连续子列和问题(Java)

1 public class test 2 { 3 public static void main(String[] args)

矫情吗；*/ 2021年12月24日 17:33/ 0 赞/ 253 阅读