题目粗心:
给定一个序列,需要求出该序列的最大子序列和及其第一个数字和最初一个数字,如果所有的数字都是正数,输入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;}