蓝桥杯练习题G

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=6

题目描述
对于给定序列a1,a2,a3……an,寻找它的某个连续子段,使得其和最大。如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20。

输入
第一行代表整数的个数n,n < 100. 第二行为n个整数

输出
输出数据为一行,包含一个整数,代表最大的子段和。(结尾加一个换行符)

1
2
3
4
样例输入
6 -2 11 -4 13 -5 -2
样例输出
20

思路:
我们要找出这些数的最大连续子串,我算法的思想是一个一个添加,从头开始添加,我们把情况定为2种情况,上一段最大子串和+当前数值 和 当前数值进行比较,取最大值
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int main()
{
int n;
int a[100];
cin >> n;
int max=0;
int final_max=-9999;
for (size_t i = 0; i < n; i++)
{
cin >> a[i];
}
for (size_t i = 0; i < n; i++)
{
if (a[i] == 0)max = a[0];
else {
max = max + a[i]>a[i] ? max + a[i] : a[i];
}
if (max>final_max)final_max = max;
}
cout << final_max;
return 0;
}