题目:HDU 1003 Max Sum
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Sample Output
Case 1: 14 1 4 Case 2: 7 1 6
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*最大连续最大子段和
* 参数:
* a[] 输入数组
* n 数组元素个数
* start, end 返回的最大子段和的起始和结束位置
*/
int maxsum(int a[], int n, int &start, int &end)
{
int tmp = a[0];
int max = a[0];
int i, tmpstart = 0, tmpend = 0;
start = 1;
end = 1;
for(i = 1; i < n; i++)
{
if(tmp >= 0) //可以是>0 也可以是>=0,看怎么要求
{
tmp += a[i];
tmpend = i;
}
else
{
tmp = a[i];
tmpstart = i;
tmpend = i;
}
if(max < tmp)
{
start = tmpstart + 1;
end = tmpend + 1;
max = tmp;
}
}
return max;
}
int main()
{
int tc, n, tmp;
int start, end;
int max;
int i, j;
int a[100001];
scanf("%d", &tc);
for(j = 0; j < tc; j++)
{
scanf("%d", &n);
for( i = 0; i < n; i++)
scanf("%d", &a[i]);
max = maxsum(a, n, start, end);
printf("Case %d:\n", j + 1);
printf("%d %d %d\n", max, start, end);
if(j != tc - 1)
printf("\n");
}
return 0;
}
分享到:
相关推荐
以上就是从给定文件中提炼出来的核心知识点,包括单调递增子序列、最大连续子段和的基本概念、应用场景、解决方法以及相关的 C++ 编程语言基础知识。通过这些知识点的学习和理解,可以帮助我们更好地掌握这类问题的...
在编程领域,最大子段和(Maximum Subarray Sum)是一个经典的问题,它的目标是找到一个数组中的连续子数组,使得其元素之和最大。这个问题在实际应用中有着广泛的应用,例如在金融分析、数据挖掘等领域。本文将详细...
最大子段和问题是一个经典的计算机科学问题,主要涉及算法设计和优化。动态规划是一种有效解决这类问题的方法,它通过构建一个最优子结构来避免重复计算,从而提高算法效率。在这个问题中,我们要在一系列整数中找到...
最大子段和问题是一个经典的计算机科学中的算法问题,它的目标是找到一个整数数组中连续子数组的最大和。这个问题在很多实际应用中都有所体现,比如在数据分析、股票投资策略等领域。下面我们将深入探讨解决这一问题...
算法分析与设计最近对问题最大子段和(分治法最大子段和动态规划) 最近对问题最大子段和(分治法)是算法设计与分析中一个重要的知识点,它是指在一组点集中找到最近对点的距离。该问题可以通过分治法和动态规划来...
最大子段和问题是一个经典的计算机科学问题,它涉及到在给定的一序列整数中找到一个连续子序列,使得这个子序列的和最大。这个问题在数组处理、数据分析和算法设计等领域有广泛的应用。本文将深入探讨三种不同的解决...
最大子段和(Maximum Subarray Problem)是一个经典的计算机科学问题,它要求在给定的一组整数序列中找到一个连续子序列,使得其和最大。这个问题在数组分析、数据分析以及股票市场预测等场景中有广泛应用。最著名的...
最大子段和问题是一个经典的计算机科学问题,它在数组或序列中寻找连续子序列的和,使得这个和最大。在给定的标题“最大子段和的分治法源程序和PPT”中,我们可以了解到这是一个关于如何使用分治算法解决最大子段和...
最大子段和问题是一个经典的计算机算法问题,它旨在找出一个数组中连续子数组的最大和。在Java中,我们可以使用动态规划或分治法这两种高效的方法来解决这个问题。 首先,我们来了解一下动态规划(Dynamic ...
最大子段和问题的核心是找到一个数组中连续子数组(子段)的和,使得这个和最大。这个问题在实际应用中有很多用途,例如在金融数据分析中寻找一段时期内的最大收益。解决这个问题的一个常见算法是Kadane's algorithm...
最大子段和问题在计算机科学领域是一个经典的动态规划问题,主要应用于寻找一组数值中的最大连续子数组之和。这个问题在数据分析、信号处理、金融分析等多个领域都有广泛的应用。接下来,我们将深入探讨最大子段和...
最大子段和问题是一个经典的计算机科学中的算法问题,它源于数论和动态规划领域。这个问题的基本目标是从一个整数序列中找到一个连续子序列(子数组),使得子序列中的元素相加得到的最大和。这个最大和可以是正数、...
最大子段和问题通常指的是在给定的一个整数数组中,找出一个连续子数组,使得该子数组的元素之和最大。这是一个经典的计算机科学问题,在算法设计与分析领域有着重要的应用。 #### 分治法简介 分治法是一种强大的...
最大子段和(Maximum Subarray Problem)是计算数组中连续子数组的最大和的经典问题。在实际应用中,这个问题广泛存在于数据挖掘、股票投资分析等领域,寻找连续子数组的最优策略具有重要意义。 一、动态规划法 ...
求一个字符串中连续最大子段和,数值可以为负数,必须是整数,算法设计与分析中的典型算法
### 最大子段和及其升级版 #### 一、基本概念与原理 **最大子段和**(Maximum Subarray Sum)问题在计算机科学领域中属于一个经典的动态规划问题。问题的核心在于从给定的一组数字中找出连续子数组,使得该子数组...
最大子段和问题(Maximum Subarray Problem)是计算机科学中的经典问题,它的目标是在一个整数数组或序列中找到连续子序列,使得该子序列的和最大。例如,给定序列[-2, 1, -3, 4, -1, 2, 1, -5, 4],最大子序列和为6...
最大子段和问题在实际中有很多应用,例如在股票交易策略中寻找最大收益的买入卖出时机,或者在处理数据流时找出一段连续时间内的最大值等。此外,这个问题还可以进行多种变体,如寻找最大非连续子数组和,或者要求子...