## HDOJ 1003：求一串数字中和最大的连续子串 原

北风其凉

``````#include<iostream>

using namespace std;

int main()
{
int counter;     //计数器
int countera;    //计数器a，用于统计一共有多少组数据
int counterb;    //计数器b，用于统计每组数据中的数据数
int i, j;        //for语句遍历用变量
int sum;         //临时计算的各数字和
int maxsum;      //数字串中的最大子串和
int left, right; //取最大子串和时的左边界和右边界

cin >> countera;
for(counter = 1; counter <= countera; counter++)
{
maxsum = -1001;

//依次读入数据时，maxsum被设置为数组中的最大值
cin >> counterb;
int* array = new int[counterb];
for(i = 0; i < counterb; i++)
{
cin >> array[i];
if(array[i] > maxsum)
{
maxsum = array[i];
left = i;
right = i;
}
}

for(i = 0; i < counterb; i++)
{
//除了自己单独成串的情况（前面已经考虑过）
//负数不能作为max子串的第0项
if(array[i] < 0)
{
continue;
}

//考察从数组array第i项开始的各子串
sum = 0;
for(j = i; j < counterb; j++)
{
sum += array[j];
//子串数字和大于maxsum的情况下
//将maxsum与左右边界设定为当前状态
if(sum > maxsum)
{
maxsum = sum;
left = i;
right = j;
}
//如果sum小于0，则后面的子串不必考察
//因为后面的串再大，加上前面小于0的sum也是累赘
//不可能再得出新的最大子串
if(sum < 0)
{
break;
}
}
}

//输出计算结果
cout << "Case " << counter << ':' << endl;
cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;
if(counter != countera)
{
cout << endl;
}
}

return 0;
}``````

``````#include<iostream>

using namespace std;

int main()
{
int counter, countera, counterb;
int i, j, k, sum, maxsum, left, right;

//读取数据组数
cin >> countera;
for(counter = 1; counter <= countera; counter++)
{
//依次读入各组数据
cin >> counterb;
int* array = new int[counterb];
for(i = 0; i < counterb; i++)
{
cin >> array[i];
}

maxsum = array[0];
//逐个子串比对
for(i = 0; i < counterb; i++)
{
for(j = i; j < counterb; j++)
{
//计算子串数字和
sum = 0;
for(k = i; k <= j; k++)
{
sum += array[k];
}
//数字和大于maxsum则更新maxsum
if(sum > maxsum)
{
left = i;
right = j;
maxsum = sum;
}
}
}

cout << "Case " << counter << ':' << endl;
cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;
if(counter != countera)
{
cout << endl;
}
}

return 0;
}``````

END

### 北风其凉

2017/12/22
0
0
Android 面试文档分享

2017/11/10
0
0

2018/02/24
0
0

messud4312
2018/04/12
0
0

RAY_STONE
2013/06/20
176
5

GMTC2019|闲鱼-基于Flutter的架构演进与创新

27分钟前
2
0

近来,华为创始人任正非多次提及人工智能。即便在华为生死攸关的关键时刻,任正非依旧不忘强调教育的重要性,“如果不重视教育,实际上我们会重返贫穷的,因为这个社会,最终是要走向人工智能的...

28分钟前
0
0
iOS开发之EventKitUI框架的应用

iOS开发之EventKitUI框架的应用 前面博客，有介绍EventKit这个框架的使用，使用EventKit可以与系统的日历和提醒应用进行交互，读写用户的日程事件。EventKitUI，顾名思义，其实基于EventKit框...

36分钟前
0
0

37分钟前
0
0
WebService学习笔记

53分钟前
2
0