这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
经典的DP!
思路: 求最大子序列这个问题已经可以说是DP的代表了。 方法我在代码的相应位置已经注释了“重点!”。 大家可以去分析下。 另外,此题多了2个特殊地方:全负则为0和第一与最后的元素。 所以增加额外记录位置的变量。
直接发代码了:
#include
using namespace std;
// Author: Tanky Woo
// HDOJ 1231
// 78MS 220K 818B
int arr[10000];
int a, b, sum, n;
int main()
{
// www.wutianqi.com
while(scanf("%d", &n;) && n)
{
memset(arr, 0, sizeof(arr));
for(int i = 0; i < n; ++i)
scanf("%d", &arr;[i]);
int flag = 0;
for(int i = 0; i < n; ++i)
if(arr[i] >= 0)
{
flag = 1;
break;
}
if(flag == 0)
{
printf("%d %d %d\n", 0, arr[0], arr[n-1]);
continue;
}
a = 0; b = 0;
sum = -10000;
int temp = -10000, temp_a = 0, temp_b = 0;
for(int i = 0; i < n; ++i) // 重点!
{
if(temp >= 0)
{
temp_b++;
temp += arr[i];
}
else
{
temp_a = i;
temp_b = i;
temp = arr[i];
}
if(temp > sum)
{
a = temp_a;
b = temp_b;
sum = temp;
}
}
printf("%d %d %d\n", sum, arr[a], arr[b]);
}
return 0;
}