当前位置:网站首页>PAT Advanced 1007 Maximum Subsequence Sum

PAT Advanced 1007 Maximum Subsequence Sum

2021-01-23 21:10:38 tanknee

subject

1007 Maximum Subsequence Sum (25 branch )

Given a sequence of K integers { N1, N2, ..., N**K }. A continuous subsequence is defined to be { N**i, N**i+1, ..., N**j } where 1≤ijK. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

Understanding and algorithms

The problem of classical maximal subsequence sum , But we need to find two more values : The starting and ending values of the largest subsequence , It is equivalent to asking for the position of the subsequence !

The rightmost value is easy to give , Because every time the maximum value is updated, this value is updated , Don't think too much about it .

The problem is how to find the starting value ?

I think a lot about it here , Later, I felt that I was worried too much ! Just grab a point :

When the previous subsequence cannot be the largest subsequence , Update the subscript of the starting value (temp_index)! So how do we know that this subsequence can't be the largest subsequence ? Its sum is less than zero , No matter how large the value is, this feature appears , Just add the front part , It would be smaller than not adding this part , So we should just give up , Go to the next subsequence search ! So we can set the starting subscript of the next search to i+1, there i For iteration variables !

Because the update time points of these two subscripts are mutually exclusive , It's impossible to update at the same time , So want to use else if Connect , Otherwise, it will result in wrong output !

Code implementation

#include <iostream>
#include <vector>

using namespace std;
int main() {
    int count;
    cin >> count;
    vector<int> v(count);
    //  The maximum value is... By default -1, It is convenient to judge whether the maximum value is found 
    //  The initial value of left and right subscripts is the left and right subscripts of the entire array !
    int max = -1, temp_max = 0, temp_index = 0, left = 0, right = count - 1;
    for (int i = 0; i < count; ++i) {
        cin >> v[i];
        temp_max += v[i];
        //  If sum is less than zero , So if you go down, it won't be the largest subsequence !
        if (temp_max < 0) {
            //  Reset temporary maximum variable 
            temp_max = 0;
            //  Then move the subscript to the next value 
            temp_index = i + 1;
        } else if (temp_max > max) {
            //  If you find a bigger one and , Just record the maximum and left and right subscripts , Because of ups and downs, the left subscript will always change , Just use temp_index As a subscript 
            max = temp_max;
            left = temp_index;
            right = i;
        }
    }
    //  If the maximum value is less than 0, So it means that we didn't find anything larger than 0 The maximum of , Set it to 0!
    if (max < 0) max = 0;
    cout << max << " " << v[left] << " " << v[right];
    return 0;
}

版权声明
本文为[tanknee]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210123210947267E.html

随机推荐