最大子段和问题

妖狐艹你老母 2024-03-17 09:53 63阅读 0赞

### 最大子段和问题 ###

#### 描述 ####

**给定由n个整数(可能为负整数)组成的序列a1，a2， a3… ， an， 寻找它的某个连续子段，使得其和最大。例如( -2,11,-4,13,-5,-2 )最大子段是\{ 11,-4,13 \}其和为20。‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬**

#### 输入 ####

**由键盘输入数组(如int a\[6\]) 的元素值‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬**

#### 输出 ####

**输出最大连续子段和**  
![在这里插入图片描述][1c9a6272a2f24f3aa6a96e9fc0d8708b.png]  
![在这里插入图片描述][68c1cd50755d467e828f58c0287c33ae.png]

#include<iostream>
    using namespace std;
    int a[6],b[100];
    int main(){
        
    	int maxn=-1;
    	for(int i=1;i<=6;i++){
        
    		cin>>a[i];
    	}
    	b[1]=a[1];
    	for(int i=2;i<=6;i++){
        
    		b[i]=max(a[i],a[i]+b[i-1]);
    		if(b[i]>maxn){
        
    			maxn=b[i];
    		}
    	}
    	for(int i=1;i<=6;i++){
        
    		cout<<a[i]<<" ";
    		
    	}
    	cout<<endl;
    	cout<<"数组a的最大连续子段和为："<<maxn;
    	return 0; 
    }

**最大子段和问题是指在一个数列中找到一个连续子数列，使得该子数列的和最大。现在假设有一个整数序列，我们需要找出这个序列中和最大的子序列。**

下面是 C++ 实现最大子段和问题的代码示例：

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int maxSubArraySum(int arr[], int n) {
        int max_so_far = arr[0];
        int max_ending_here = arr[0];
    
        for (int i = 1; i < n; i++) {
            max_ending_here = max(arr[i], max_ending_here + arr[i]);
            max_so_far = max(max_so_far, max_ending_here);
        }
    
        return max_so_far;
    }
    
    int main() {
        int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int n = sizeof(arr) / sizeof(arr[0]);
        int maxSum = maxSubArraySum(arr, n);
        cout << "Maximum contiguous sum of the array is: " << maxSum << endl;
        return 0;
    }

**在这个代码示例中，我们使用了 Kadane 算法来解决最大子段和问题。该算法基本上是一个动态规划算法，它通过迭代计算每个元素加入子序列之后的和，如果当前元素可以改变子序列的和更大，则将子序列加上当前元素。**

**算法的时间复杂度是 O(n)。**

[1c9a6272a2f24f3aa6a96e9fc0d8708b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/1342577078e84266b55c42f9d1b7be3d.png
[68c1cd50755d467e828f58c0287c33ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/347330f4489c4a3382454fdcc8411e29.png