/*
hdoj 1231-最大连续子序列
written by lky
lky 125MS 0K 709B C++ 2008-03-06 21:53:58
动态规划:最大连续子序列,要求输出序列的第一个和最后一个元素
p[i]为输入数
b[i]为当前元素所在序列的第一个元素
sum[i]为当前元素所在序列的最大值
*/
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
int p[10001], b[10001], sum[10001];
int n, i, j;
int Max, t;
bool flag;
int temp;
while (scanf("%d", &n) != EOF && n)
{
flag = false;
t = Max = 0;
temp = 0;
for (i=0; i<n; ++i)
{
scanf("%d", &p[i]);
if(p[i] >= 0)
flag = true;
if(t > 0) t += p[i], b[i] = temp;
else t = p[i], b[i] = temp = i;
sum[i] = t;
if(t > Max) Max = t;
}
if(!flag)
printf("0 %d %d/n", p[0], p[n-1]);
else
{
for (i=0; i<n; ++i)
{
if(sum[i] == Max)
{
printf("%d %d %d/n",Max, p[b[i]], p[i]);
break;
}
}
}
}
return 0;
}
hdoj 1231-最大连续子序列
written by lky
lky 125MS 0K 709B C++ 2008-03-06 21:53:58
动态规划:最大连续子序列,要求输出序列的第一个和最后一个元素
p[i]为输入数
b[i]为当前元素所在序列的第一个元素
sum[i]为当前元素所在序列的最大值
*/
#include<iostream>
#include <algorithm>
using namespace std;
int main()
{
int p[10001], b[10001], sum[10001];
int n, i, j;
int Max, t;
bool flag;
int temp;
while (scanf("%d", &n) != EOF && n)
{
flag = false;
t = Max = 0;
temp = 0;
for (i=0; i<n; ++i)
{
scanf("%d", &p[i]);
if(p[i] >= 0)
flag = true;
if(t > 0) t += p[i], b[i] = temp;
else t = p[i], b[i] = temp = i;
sum[i] = t;
if(t > Max) Max = t;
}
if(!flag)
printf("0 %d %d/n", p[0], p[n-1]);
else
{
for (i=0; i<n; ++i)
{
if(sum[i] == Max)
{
printf("%d %d %d/n",Max, p[b[i]], p[i]);
break;
}
}
}
}
return 0;
}