关于算法-数据结构:PAT甲级1007-Maximum-Subsequence-Sum

题目粗心：

给定一个序列，需要求出该序列的最大子序列和及其第一个数字和最初一个数字，如果所有的数字都是正数，输入 0 和第一个数字及其最初一个数字。

算法思路：

算法思路 1（暴力递归）：

如上图所示，实际上该问题，等价与初始和为 0，获得每一个数字作为终点的所有子序列和的最大值中的最大值，如图中所标注的 20. 间接应用深度优先搜寻解决。代码如下：

/*
 * index 为以后所抉择的数字下标 * sum 为 [i,index] 的子序列和，其中 i 为终点 
 */
int DFS(const int *nums,int N,int index,int sum){// [i,index+1]的最大子序列和
    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;
}

因为该办法会导致一个测试点超时，而且不太好求解左右端点，这里不再给出残缺代码，然而其搜寻过程值得借鉴，也是接下来优化的根据。

算法思路 2(双重循环)：

咱们枚举每一个左端点 i，应用 temp 记录以后端点 i 的每一个子序列和，并应用 max_sum 记录所有子序列和中的最大值，L 和 R 为其左右下标，而后应用 j 遍历每一个右端点，起始为 i，每一次 temp 累加 nums[j]，判断 temp 是否大于 max_sum，如果是，就更新 max_sum，L,R。最初依据 max_sum 进行输入即可。代码如下：

int max_sum = nums[0];
int L=0,R=0;
for(int i=0;i<N;++i){
    int temp = 0;// 暂存每一个终点的局部子序列和
    for(int j=i;j<N;++j){temp += nums[j];
        if(temp>max_sum){
            max_sum = temp;
            L = i;
            R = j;
        }
    }
}

算法思路 3(动静布局)：

仔细观察下面的图就晓得，在最右边的抉择，肯定是蕴含了左边的抉择的，也即是说，如果右边的抉择在某个时刻选了一个正数，而下一个抉择是一个负数，咱们齐全能够将后面抉择的最大子序列和舍弃掉，为什么呢？因为下一个抉择的负数，恰好是左边第一个抉择的数字，其前面的后果肯定比右边的后果大，比方后面 2 条分支，最开始抉择了 - 2 和 11，右边的那支在抉择 - 2 之后的下一次抉择就是 11，正好是左边以后的抉择，那么右边的抉择的数字的最大子序列和 =-2+ 左边抉择的数字的最大子序列和，天然就没有必要还要保留之前抉择的小于 0 的子序列和。
咱们能够应用一个数组 dp[n]保留从终点 (不确定，因为会呈现舍弃后会从新的终点开始) 到以后数字 n 的最大子序列和，如果后面的子序列和小于 0，就舍弃 dp[n-1], 让 dp[n]=nums[n] 即可，如果 dp[n-1]大于等于 0，就保留dp[n]=dp[n-1]+nums[n]（因为它可能会让前面的子序列和更大），这样就失去了前一个状态和后一个状态的关系，初始状态为dp[0]=nums[0]。代码如下：

int dp[N];
dp[0] = nums[0];
int max_sum = nums[0];
int L=0,R=0;// 最大子序列的左和右端点
int left=0,right=0;// 以后子序列的左和右端点
for (int j = 1; j < N; ++j) {if(dp[j-1]>0){// 后面的 [0,j-1] 的子序列和大于 0，就讲其加到以后数字上作为 [0,j] 的最大子序列和
        dp[j] = dp[j-1] + nums[j];
        right = j;// 只扭转了右端点
    } else {dp[j] = nums[j];// 扭转了左端点和右端点
        left = j;
        right = j;
    }
    if(dp[j]>max_sum){// 记录最大子序列和及其左右端点
        max_sum = dp[j];
        L = left;
        R = right;
    }
}

其过程如下图：

提交后果：

AC 代码 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;// 暂存每一个终点的局部子序列和
        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 代码 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;// 最大子序列的左和右端点
    int left=0,right=0;// 以后子序列的左和右端点
    for (int j = 1; j < N; ++j) {if(dp[j-1]>0){// 后面的 [0,j-1] 的子序列和大于 0，就讲其加到以后数字上作为 [0,j] 的最大子序列和
            dp[j] = dp[j-1] + nums[j];
            right = j;// 只扭转了右端点
        } else {dp[j] = nums[j];// 扭转了左端点和右端点
            left = j;
            right = j;
        }
        if(dp[j]>max_sum){// 记录最大子序列和及其左右端点
            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;
}