Hugh

门泊东吴万里船

0%

PAT-1007 Maximum Subsequence Sum

Posted on Edited on In

1007 Maximum Subsequence Sum

题意

给定一个数列，计算每个这个序列最大子序列的和

思路

计算每个点为终点的最大子序列和
maxSeqSum[i] = max(num[i], maxSeqSum[i - 1] + num[i])

源码

line_number: true
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
#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
struct ST_MAX_SUM_SEQUENCE{ //记录最大子序列和
    int iStartIndex;
    int iEndIndex;
    int iSum;
};
int main()
{
    int iK;
    scanf("%d", &iK);

    int szNum[iK];
    ST_MAX_SUM_SEQUENCE stMaxSumSequence[iK]; //记录每个位置子序列和
    ST_MAX_SUM_SEQUENCE stMaxSum; //记录和最大的子序列
    stMaxSum.iStartIndex = 0;
    stMaxSum.iEndIndex = 0;
    cin>>szNum[0];
    stMaxSum.iSum = szNum[0];

    stMaxSumSequence[0].iStartIndex = 0;
    stMaxSumSequence[0].iEndIndex = 0;
    stMaxSumSequence[0].iSum = szNum[0];
    for(int i = 1; i < iK; i++)
    {
        cin >> szNum[i];

        if(szNum[i] + stMaxSumSequence[i - 1].iSum >= szNum[i])
        {
            stMaxSumSequence[i].iStartIndex = stMaxSumSequence[i - 1].iStartIndex;
            stMaxSumSequence[i].iEndIndex = i;
            stMaxSumSequence[i].iSum = szNum[i] + stMaxSumSequence[i - 1].iSum;
        }
        else
        {
            stMaxSumSequence[i].iStartIndex = i;
            stMaxSumSequence[i].iEndIndex = i;
            stMaxSumSequence[i].iSum = szNum[i];
        }

        if (stMaxSum.iSum < stMaxSumSequence[i].iSum)
        {
            stMaxSum.iStartIndex = stMaxSumSequence[i].iStartIndex;
            stMaxSum.iEndIndex = stMaxSumSequence[i].iEndIndex;
            stMaxSum.iSum = stMaxSumSequence[i].iSum;
        }
    }

    if(stMaxSum.iSum < 0)
    {
        cout<< 0 << " " << szNum[0] << " " << szNum[iK - 1] <<endl;
    }
    else
    {
        cout<< stMaxSum.iSum << " " << szNum[stMaxSum.iStartIndex] << " " << szNum[stMaxSum.iEndIndex] <<endl;
    }
    return 0;
}