《数据结构》01-复杂度2 Maximum Subsequence Sum

喜欢ヅ旅行 2022-05-08 11:56 154阅读 0赞

# 题目 #

Given a sequence of K integers \{ N 1 \_1 1 , N 2 \_2 2 , …, N K \_K K \}. A continuous subsequence is defined to be \{ N i \_i i , N i + 1 \_\{i+1\} i\+1 , …, N j \_j j \} where  1 ≤ i ≤ j ≤ K 1≤i≤j≤K 1≤i≤j≤K. 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

# 分析 #

[最大子列和问题][Link 1]加难版  
翻译过来就是求一个序列的最大子列和，并输出最大子列和的开头和结尾的数，求最大子列和我们用到了"贪心法"，累加当前序列，如果序列和小于 0 就置 0 重新累加，否则更新最大值。  
现在的问题是如何记录开头和结尾的数，结尾的数，就是每次更新最大值时记录当时的序列号，该序列号存的值就是结尾的数；而开头的数和每次序列和小于 0 相关，每次序列和清零表示抛弃了这段子序列，之后有新的开始，所以清 0 后下一个序列号里存的就是子序列开头的数，那么如何记录下这个数？对了，更新最大值的时候！每次更新最大值相当于固定一段子序列  
最后一个问题就是，当只有一个 0，其余全为负数的情况，按道理应该输出全 0，但是实际输出的是 “0 第一个数 最后一个数”，为了避免这种情况，我们将最大值初值赋为 -1，这样遇到 0 时也能更新最大值

#include<iostream>
    using namespace std;
    int main(){
        
    	int n;
    	int a[100000+5];
    	cin>>n;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	int left = 0;
    	int tmpleft = 0;
    	int right = n-1;
    	int max =0;
    	int tmpSum=0;
    	for(int i=0;i<n;i++){
        
    		tmpSum+=a[i];
    		if(tmpSum<0){
        
    			tmpSum=0;
    			tmpleft = i+1;   // 开头的数就在这段被抛弃子序列的下一个 
    		}else if(max < tmpSum){
        
    			max = tmpSum;        
    			left = tmpleft;   // 每次更新最大值也就确定了一段子序列，保存此时的开头 
    			right = i;       // 结尾的数就在每次更新最大值时 
    		}
    	}
    	if(max>=0)
    		cout<<max<<" "<<a[left]<<" "<<a[right];
    	else
    		cout<<0<<" "<<a[0]<<" "<<a[n-1];
    	return 0;
    }

[Link 1]: https://blog.csdn.net/liyuanyue2017/article/details/82990246