PAT_ Grade A_ 1007 Maximum Subsequence Sum

2020-12-08 14:44:08

The main idea of the topic ：

Given a sequence , The first and the last subsequence of the number and its largest subsequence , If all the numbers are negative , Output 0 And the first number and its last number .

Algorithm ideas ：

Algorithm ideas 1（ Recurrence of violence ）： As shown in the figure above , In fact, the problem , Equivalence and initial sum are 0, Get the maximum of the sum of all subsequences starting with each number , As marked in the picture 20. Directly use depth first search to solve . The code is as follows ：

/*
* index Subscript the currently selected number  * sum by [i,index] Subsequence sum of , among i As a starting point
*/
int DFS(const int *nums,int N,int index,int sum){
// [i,index+1] The largest subsequence of and
int current = -0x7fffffff;
if(index+1<N){
current = DFS(nums,N,index+1,sum+nums[index+1]);
}
return max(sum,current);
}

int process(const int *nums,int N,int index){
int max_sum = nums[index];
for (int i = index; i < N; ++i) {
int next = DFS(nums,N,i,nums[i]);
max_sum = max(max_sum,next);
}
return max_sum;
}

Because this method will cause a test point to time out , And it's not very easy to solve the left and right endpoints , The complete code is no longer given here , But its search process is worth learning from , It's also the basis for the next optimization .

Algorithm ideas 2( Double cycle )：

Let's enumerate each left endpoint i, Use temp Record the current endpoint i Each subsequence of and , And use max_sum Record the maximum value in the sum of all subsequences ,L and R For its left and right subscripts , And then use j Traverse every right endpoint , Starts i, every time temp Add up nums[j], Judge temp Is it greater than max_sum, If it is , Just update max_sum,L,R. According to the max_sum Just output . The code is as follows ：

int max_sum = nums;
int L=0,R=0;
for(int i=0;i<N;++i){
int temp = 0;//  Hold the partial subsequence of each starting point and
for(int j=i;j<N;++j){
temp += nums[j];
if(temp>max_sum){
max_sum = temp;
L = i;
R = j;
}
}
}
Algorithm ideas 3( Dynamic programming )：

A close look at the picture above shows that , The choice on the far left , It must have included the selection on the right , That is said , If the choice on the left picks a negative number at a certain time , And the next choice is a positive number , We can discard the largest subsequence and discard it , Why? ？ Because the positive number of the next choice , It happens to be the first selected number on the right , The result behind it must be bigger than the result on the left , Like the front 2 Branches , At first, I chose -2 and 11, The one on the left is choosing -2 The next choice after that is 11, It's the current choice on the right , Then the largest subsequence of the selected number on the left and =-2+ The largest subsequence of the number selected on the right and , Naturally, there is no need to keep the previous selection less than 0 Subsequence sum of .
We can use an array dp[n] Save from the beginning ( Not sure , Because there will be a new starting point after abandonment ) To the current number n The largest subsequence of and , If the sum of the preceding subsequences is less than 0, Give up dp[n-1], Give Way dp[n]=nums[n] that will do , If dp[n-1] Greater than or equal to 0, Just keep it dp[n]=dp[n-1]+nums[n]（ Because it might make the subsequences later and larger ）, So we get the relationship between the former state and the latter state , The initial state is dp=nums. The code is as follows ：

int dp[N];
dp = nums;
int max_sum = nums;
int L=0,R=0;//  The left and right endpoints of the largest subsequence
int left=0,right=0;//  The left and right endpoints of the current subsequence
for (int j = 1; j < N; ++j) {
if(dp[j-1]>0){
//  Ahead [0,j-1] The sum of subsequences of is greater than 0, Just add it to the current number as [0,j] The largest subsequence of and
dp[j] = dp[j-1] + nums[j];
right = j;//  Only the right endpoint has been changed
} else {
dp[j] = nums[j];//  Changed left and right endpoints
left = j;
right = j;
}
if(dp[j]>max_sum){//  Record the maximum subsequence sum and its left and right endpoints
max_sum = dp[j];
L = left;
R = right;
}
}

The process is as follows ： Submit results ： AC Code 1：

#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
int N;
scanf("%d",&N);
int nums[N];
for (int i = 0; i < N; ++i) {
scanf("%d",&nums[i]);
}
int max_sum = nums;
int L=0,R=0;
for(int i=0;i<N;++i){
int temp = 0;//  Hold the partial subsequence of each starting point and
for(int j=i;j<N;++j){
temp += nums[j];
if(temp>max_sum){
max_sum = temp;
L = i;
R = j;
}
}
}
if(max_sum>=0){
printf("%d %d %d",max_sum,nums[L],nums[R]);
} else {
printf("0 %d %d",nums,nums[N-1]);
}
return 0;
}

AC Code 2：

#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
int N;
scanf("%d",&N);
int nums[N];
for (int i = 0; i < N; ++i) {
scanf("%d",&nums[i]);
}
int dp[N];
dp = nums;
int max_sum = nums;
int L=0,R=0;//  The left and right endpoints of the largest subsequence
int left=0,right=0;//  The left and right endpoints of the current subsequence
for (int j = 1; j < N; ++j) {
if(dp[j-1]>0){
//  Ahead [0,j-1] The sum of subsequences of is greater than 0, Just add it to the current number as [0,j] The largest subsequence of and
dp[j] = dp[j-1] + nums[j];
right = j;//  Only the right endpoint has been changed
} else {
dp[j] = nums[j];//  Changed left and right endpoints
left = j;
right = j;
}
if(dp[j]>max_sum){//  Record the maximum subsequence sum and its left and right endpoints
max_sum = dp[j];
L = left;
R = right;
}
}
if(max_sum>=0){
printf("%d %d %d",max_sum,nums[L],nums[R]);
} else {
printf("0 %d %d",nums,nums[N-1]);
}
return 0;
}

https://chowdera.com/2020/12/20201208144338710j.html