当前位置:网站首页>PAT_ Grade A_ 1007 Maximum Subsequence Sum

PAT_ Grade A_ 1007 Maximum Subsequence Sum

2020-12-08 14:44:08 Qiao Zixin

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 ):

 screenshots 2020-12-08  Afternoon 2.16.29.png
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[0];
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[0]=nums[0]. The code is as follows :

int dp[N];
dp[0] = nums[0];
int max_sum = nums[0];
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 :
 screenshots 2020-12-08  Afternoon 2.36.33.png

Submit results :

 screenshots 2020-12-08  Afternoon 2.37.25.png

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[0];
    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[0],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[0] = nums[0];
    int max_sum = nums[0];
    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[0],nums[N-1]);
    }
    return 0;
}

版权声明
本文为[Qiao Zixin]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208144338710j.html