最大子段和问题

心已赠人 2023-10-05 13:29 21阅读 0赞

**最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。 例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11,-4,13,-5,-2）时，最大子段和为: a2+a3+a4=20**

输入格式:  
第一行输入整数个数n（1≤n≤10000），再依次输入n个整数。

输出格式:  
输出第一行为最大子段和，第二行为子段第一个数和最后一个数在整个序列中的位序。

输入样例1:

6
    -2 11 -4 13 -5 -2

输出样例1:

20
    2 4

**源程序：**

#include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    int main()
    {
        
    	vector<int> que;
    	int n, i, temp;	
    	
    	//输入数据
    	cin >> n;
    	for (i = 0; i < n; i++) {
        
    		cin >> temp;
    		que.push_back(temp);
    	}
    
    	//遍历查找是否有正数
    	bool  flag=false;
    	for (i = 0; i < n; i++) {
        
    		if (que[i] > 0) {
        
    			flag = true;
    			break;
    		}
    	}
    
    	if (flag) {
        
    		//算法设计采用窗口大小变化和位置移动的思想，所以用窗口表示子段
    
    		int max = 0, sum = 0;  //设置最大值，求和值
    		int front;  //窗口起始位置，下标
    		int begin, end;   //窗口始末位置
    	
    		for (int k = n; k > 1; k--)  //窗口大小控制，写程序时可以先固定n的值比较好理解
    		{
        
    			//窗口起始位移动控制，即固定长度的子数组
    			for (front = 0; front <= n - k; front++) 
    			{
        
    				sum = 0;   //重置每次窗口内数组之和
    
    				//窗口内数组之和
    					for (i =front; i <front + k; i++) 
    						sum += que[i];					
    
    					//当前最大值信息记录
    					if (sum > max) 
    					{
        
    						max = sum;
    						//记录当前最大值的窗口的始末下标
    						begin = front+1;    //加1为了对应在序列中的位置
    						end = front + k;    //窗口末位=下标+窗口长度，不用+1
    					}
    			}
    		}
    
    		cout << max << endl;
    		cout << begin<<" "<<end<<endl;
    	}
    	else{
        
    			cout << "0" << endl;
    	}
    	
    	return 0;
    }