hdu

最大子段和

题目链接
Max Sum

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 211834 Accepted Submission(s): 49757

Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1:
14 1 4

Case 2:
7 1 6

数组a[left … right]的最大子段和无非有三种情况,

  1. 最大子段和在a[left … mid]中;
  2. 在a[mid … right]中;
  3. 在(1) 和 (2) 之间.
    可利用分治算法, 时间复杂度为O(nlogn).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<cmath>
#include<cstdlib>
#define MAX 100005
#define MIN -1001

using namespace std;

int a[MAX];

/**
* 最大子段和结构体
* maxSum idxStart, idxEnd
*/
typedef struct Node
{
    int maxSum;
    int idxStart, idxEnd;
    Node()
    {
        maxSum = MIN;
        idxStart = idxEnd = 0;
    }
    void init(int ms, int is, int ie)
    {
        maxSum = ms;
        idxStart = is;
        idxEnd = ie;
    }
    bool operator > (const Node node) const
    {
        return maxSum > node.maxSum;
    }
} Answer;

/**
* @name fun 
* A[left ... right] 的最大子段和
*/
Answer fun(int *A, int left, int right)
{
    if(left == right)
    {
        Answer ans;
        ans.init(A[left], left, left);
        return ans;
    }
    int mid = (left+right) >> 1;
    Answer leftAns = fun(A, left, mid);
    Answer rightAns = fun(A, mid+1, right);
    leftAns = leftAns > rightAns?leftAns:rightAns;
    Answer midLeftSum, midRightSum, midAns;
    for(int i=mid, ts = 0; i>=left; i--)
    {
        ts += A[i];
        if(ts >= midLeftSum.maxSum)
        {
            midLeftSum.init(ts, i, mid);
        }
    }
    for(int i=mid+1, ts = 0; i<=right; i++)
    {
        ts += A[i];
        if(ts >= midRightSum.maxSum)
        {
            midRightSum.init(ts, mid+1, i);
        }
    }
    midAns.init(midLeftSum.maxSum+midRightSum.maxSum, midLeftSum.idxStart, midRightSum.idxEnd);
    return leftAns > midAns?leftAns:midAns;
}

int main()
{
    int tc, n;
    scanf("%d", &tc);
    for(int i=1; i<=tc; i++)
    {
        scanf("%d", &n);
        for(int j=0; j<n; j++)
        {
            scanf("%d", &a[j]);
        }
        printf("Case %d:\n", i);
        Answer ans = fun(a, 0, n-1);
        printf("%d %d %d\n", ans.maxSum, ans.idxStart+1, ans.idxEnd+1);
        if(i<tc)printf("\n");
    }
    return 0;
}