HDOJ 1231 最大连续子序列

这篇博客是从旧博客 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;
}