hdu 1003 Max Sum

第一個，一開始做的，比較雜亂：
[cpp] 
/* THE PROGRAM IS MADE BY PYY */ 
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.
 
    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1003
    Name  : 1003 Max Sum
 
    Date  : Thursday, July 05, 2012
    Time Stage : 1 hour
 
    Result:
6132517 2012-07-05 11:39:32 Accepted    1003
0MS 1008K   1950 B
C++ pyy
 
 
Test Data :
 
Review :
 
//----------------------------------------------------------------------------*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <vector> 
 
#include <algorithm> 
#include <iostream> 
#include <queue> 
#include <set> 
#include <string> 
 
using namespace std ; 
 
#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value 
#define max(x, y)        ((x) > (y) ? (x) : (y)) 
#define min(x, y)        ((x) < (y) ? (x) : (y)) 
 
#define INF     (0x3f3f3f3f) 
#define MAXN    100009 
 
#define L(x)    ((x)<<1) 
#define R(x)    (((x)<<1)|1) 
#define M(x, y) (((x)+(y)) >> 1) 
 
#define DB    /##/ 
typedef __int64 LL; 
 
int sum[MAXN], v[MAXN], s, t, head, tail, n, tcase; 
 
 
int main() 
{ 
    int i, j, MaxSum, FinSum; 
 
    while (scanf("%d", &tcase) != EOF) 
    { 
        for (j = 1; j <= tcase; ++j) 
        { 
            scanf("%d", &n); 
            for (i = 0; i < n; ++i) 
            { 
                scanf("%d", v+i); 
                if(0 == i) 
                { 
                    FinSum = sum[i] = v[i]; 
                    s = t = head = tail = i; 
                } 
                else 
                { 
                    if (sum[i-1] < 0) 
                    { 
                        head = tail = i; 
                        sum[i] = v[i]; 
                    } 
                    else 
                    { 
                        int tmp = sum[i-1] + v[i]; 
//                      if (tmp >= 0)//只有大於0的值才可能+後面的數變成更大的數 
//                      { 
                            sum[i] = tmp; 
                            tail = i; 
//                      } 
/*                      else// 若加起來的值為負數，則不如不加
                        {
                            sum[i] = v[i];
                            head = tail = i;
                        }
*/ 
                    } 
                    if (FinSum < sum[i]) 
                    { 
                        s = head; 
                        t = tail; 
                        FinSum = sum[i]; 
                    } 
                } 
            } 
            printf("Case %d:\n%d %d %d\n", j, FinSum, s+1, t+1); 
            if (j < tcase) 
                putchar('\n'); 
        } 
    } 
 
    return 0; 
} 

第二個，修改過的，參考了別人的代碼：
[cpp] 
/* THE PROGRAM IS MADE BY PYY */ 
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.
 
    URL   : 
    Name  : 
 
    Date  : Thursday, July 05, 2012
    Time Stage : 
 
    Result:
6132607 2012-07-05 12:00:59 Accepted    1003
0MS 616K    1623 B
C++ pyy
 
 
Test Data :
 
Review :
 
//----------------------------------------------------------------------------*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <vector> 
 
#include <algorithm> 
#include <iostream> 
#include <queue> 
#include <set> 
#include <string> 
 
using namespace std ; 
 
#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value 
#define max(x, y)        ((x) > (y) ? (x) : (y)) 
#define min(x, y)        ((x) < (y) ? (x) : (y)) 
 
#define INF     (0x3f3f3f3f) 
#define MAXN    100009 
 
#define L(x)    ((x)<<1) 
#define R(x)    (((x)<<1)|1) 
#define M(x, y) (((x)+(y)) >> 1) 
 
#define DB    /##/ 
typedef __int64 LL; 
 
int v[MAXN], s, t, head, n, tcase; 
 
 
int main() 
{ 
    int i, j, FinSum, CurSum; 
 
    while (scanf("%d", &tcase) != EOF) 
    { 
        for (j = 1; j <= tcase; ++j) 
        { 
            scanf("%d", &n); 
            FinSum = -100000000; 
            CurSum = head = 0; 
            for (i = 0; i < n; ++i) 
            { 
                scanf("%d", v+i); 
                CurSum += v[i]; 
                // 下面兩個if不能調換過來，否則將無法處理只有一個負數的情況 
                if (FinSum < CurSum) 
                { 
                    FinSum = CurSum; 
                    s = head; 
                    t = i; 
                } 
                if (CurSum < 0) 
                { 
                    CurSum = 0; 
                    head = i+1; 
                } 
            } 
            printf("Case %d:\n%d %d %d\n", j, FinSum, s+1, t+1); 
            if (j < tcase) 
                putchar('\n'); 
        } 
    } 
 
    return 0; 
} 
作者：panyanyany