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;
}

PAT Advanced 1007 Maximum Subsequence Sum More articles about

  1. PAT Advanced 1007 Maximum Subsequence Sum (25 branch )

    Given a sequence of K integers { N​1​​, N​2​​, ..., N​K​​ }. A continuous subsequence is defined to ...

  2. PAT nail 1007. Maximum Subsequence Sum (25) 2016-09-09 22:56 41 Human reading Comment on (0) Collection

    1007. Maximum Subsequence Sum (25) The time limit 400 ms Memory limit 65536 kB Code length limit 16000 B The procedure of judging questions Standard author CHEN, Y ...

  3. PAT Class A 1007 Maximum Subsequence Sum (25)(25 branch )(0 It's not a negative number , Water problem )

    1007 Maximum Subsequence Sum (25)(25  branch ) Given a sequence of K integers { N~1~, N~2~, ..., N~K~ }. A ...

  4. PAT Class A 1007 Maximum Subsequence Sum

    https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168 Given a sequence of K  ...

  5. PAT Class A 1007. Maximum Subsequence Sum (25) 【 The largest substring and 】

    Topic link https://www.patest.cn/contests/pat-a-practise/1007 Ideas The largest subseries and Namely All the way back If sum < 0 Reset to 0 And then every time ...

  6. python To write PAT 1007 Maximum Subsequence Sum( violence Divide and conquer method Dynamic programming )

    python To write PAT Class A 1007 Maximum Subsequence Sum wenzongxiao1996 2019.4.3 subject Given a sequence of K integer ...

  7. PAT 1007 Maximum Subsequence Sum( The longest segment and )

    1007. Maximum Subsequence Sum (25) The time limit 400 ms Memory limit 65536 kB Code length limit 16000 B The procedure of judging questions Standard author CHEN, Y ...

  8. 1007 Maximum Subsequence Sum (PAT(Advance))

    1007 Maximum Subsequence Sum (25 branch )   Given a sequence of K integers { N​1​​, N​2​​, ..., N​K​​ }. A ...

  9. 1007 Maximum Subsequence Sum (25 branch ) Find the maximum continuous interval and

    1007 Maximum Subsequence Sum (25 branch )   Given a sequence of K integers { N​1​​, N​2​​, ..., N​K​​ }. A ...

  10. 1007 Maximum Subsequence Sum (25 branch )

    1007 Maximum Subsequence Sum (25  branch )   Given a sequence of K integers { N​1​​, N​2​​, ..., N​K​​ }. A ...

Random recommendation

  1. sql Correlation subquery

    Subquery : Queries nested in other queries . Subqueries are called internal queries , The statements that contain subqueries are called external queries All subqueries can be divided into two categories , Both Correlated subqueries and uncorrelated subqueries 1> Uncorrelated subqueries are subqueries that are independent of external queries , The total number of subqueries is ...

  2. MINIX3 Process communication analysis

    MINIX3 Process communication analysis 6.1MINIX3 Process communication profile MINIX3 The process communication of is MINIX3 The most important part of the kernel , I personally think it's actually It's in the kernel “ kernel ”, How to understand this concept ? Actually MI ...

  3. Linux Brief introduction of compiler kernel configuration options

    Code maturity level options Code maturity options Prompt for development and/or incomplete code/drivers Shows that it is still under development or not finished ...

  4. Baidu Maps SDK Download and create apps ( apply Key) And local import Demo

    One . Baidu Maps SDK download http://lbsyun.baidu.com/sdk/download?selected=location Choose all , Then download the development package separately . Sample code . Class reference . Two . Create an ( Shen ...

  5. Spring Security OAuth 2.0

    To continue · The previous <OAuth 2.0> OAuth 2.0 Provider Realization stay OAuth 2.0 in ,provider Roles actually separate authorization services from resource services , Sometimes they can be in the same application , ...

  6. Pok Use guide

    Pok Use guide POK It's an open source compliance ARINC653 Operating system of , For some reason , I'm going to start a whole new field , I hope to record the progress every day , At the same time, you are welcome to correct it . For now, let's briefly explain POK How to use it Access to the source code ...

  7. python Reptiles Crawl the list of sequential blog posts

    python It's so easy to write a reptile in import urllib.request from pyquery import PyQuery as PQ # according to URL Get the content and decode it into UTF-8 def g ...

  8. A couple of classic css skill

    Use line-height Vertical center line-height:24px; When you use a container with a fixed width and you need a line centered vertically , Use line-height that will do ( The height is the same as the parent container ), More vertical summary can be seen ...

  9. css Realize the equal scaling of the length and width of the elements

    Realize the idea ( Aspect ratio 2:1): Based on the parent element , Sub level width:100%; ( That is, the width of the parent 100%), padding-top:50% ( That is, the width of the parent 50%, according to css standard , pa ...

  10. C# The general process of callback implementation

    C# The general process of callback implementation C# Method callback mechanism of , It's based on delegation , The typical implementation process is given below . ( One ) Definition . Declaration callback Delegate void DoSomeCallBack(type para); ...