最大子序列和的详解

心已赠人 2023-10-05 14:45 12阅读 0赞

## 一.问题 ##

例：求数列的最大子段和。 给定n个元素的整数列（可以能为负整数）,a1,a2,…,an。求数列的字段，使其和最大。

例如：当(a1, a2, a3, a4, a5, a6)=(-2, 11, -4, 13, -5, -2)时，最大子段和为sum(11-4+13)=20。

## 二.解决方法 ##

我这里采用两种方法：①遍历的方法 ②分治法

### **①遍历法** ###

**原理分析：**遍历该数组，每遍历一个i元素就判断temp+a\[i\]是否大于a\[i\],如果大于就更新temp=temp+a\[i\],否则temp=a\[i\],最后temp跟当前最大子序列和maxsum比较，如果大于，则maxsum=temp；否则不更新maxsum;最后遍历完，直接返回maxsum.

**遍历法的c语言源码：**

#include<stdio.h>
    //类似于01背包问题
    int start,end;
    int MaxSubsequenceSum( int A[], int n)
    {
        int tempsum = 0;
        int maxSum = 0;
         int tstart=0,tend=0;
        for (int j = 0;j < n;j++)  //遍历数组
        {    
    		if((tempsum + A[j]) > A[j]){  //判断临时最大和+一个当前元素是否大于当前元素，如果大于，则把当前元素加进来，更新临时最大和，否则临时最大和更新为当前元素
    			tempsum=tempsum + A[j];
    			tend=j;   //更新末尾位置   
    		}
    		else{      //如果临时最大和+一个当前元素小于当前元素，则更新临时最大和
    		    tempsum=A[j];
    			tstart=j;  //更新起始位置
    
    		}
            if (tempsum > maxSum){   // 通过当前临时最大和与上一个最大和作比较，如果大于则更新最大和
                maxSum = tempsum;
    		    start=tstart;  //更新起始位置
    			end=tend;  //更新末尾位置
    		}
        }
        return maxSum;
    }
    int main()
    {
     int maxSubSum,n,i;
        int a[101]; 
        while(scanf("%d",&n)!=EOF)
        {
         for(i=0;i<n;i++)
         scanf("%d",&a[i]);
         maxSubSum = MaxSubsequenceSum(a, n);
         printf("%d %d %d\n",maxSubSum,start,end);
     }
        return 0;
    }

### ②分治法 ###

**原理分析：**此问题用二分法分解后的两个子序列（子问题）并不独立，因为有可能最长的连续不升数列正好存在于两个子序列的连接位置。

**如果将所给的序列a\[1..n\]分为长度相等的2段a\[1--(n/2)\]和a\[(n/2)+1--n\],则a\[1--n\]的最长连续不升数列有3种情况：**

1) a\[1..n\]的最长连续不升数列与a\[1..(n/2)\]的最长连续不升数列相同;

2) a\[1..n\]的最长连续不升数列与a\[(n/2)+1..n\]的最长连续不升数列相同;

3) a\[1..n\]的最长连续不升数列为∑a\[k\],且1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。

情况1和情况2可分别递归求得。 对于情况3,如果不在情况1和情况2中，则a\[(n/2)\]与a\[(n/2)+1\]一定在最优子序列中。因此,我们可以计算出a\[i..(n/2)\]的最大值s1;并计算出a\[(n/2)+1..j\]中的最大值s2。则s1+s2即为出现情况3时的最优值。

**c语言源码：**

#include<stdio.h>
    #define max 100
    int start=0;
    int end=0;
    int minsum(int a[], int left, int right) {
    	int s,s0, s1, lf, rt;
    	if (left == right)
    		return a[left];
    	else {
    		int mid = (left + right)/2;
    		int leftsum = minsum(a, left, mid);  //左子序列最大和
    		int rightsum = minsum(a, mid + 1, right);  //右子序列最大和
    		s0 = 0;  //左边临时和
    		lf = 0;
    		for(int i = mid; i >= 0; i--) {
    			lf += a[i];
    			if (lf > s0) {  //加上当前的数如果大于左边临时和，则更新左边临时和
    				s0 = lf;
    				start = i;  //起始点
    			}
    		}
    		s1 = 0;  //右边临时和
    		rt = 0;
    		for(i = mid + 1;i <= right; i++){
    			rt += a[i];
    			if (rt > s1) {
    				s1 = rt;
    				end = i;  //末尾点
    			}
    		}
    		s = s0 + s1;
    		if (s< leftsum&&rightsum < leftsum)
    			return leftsum;
    		else if (s<rightsum&&rightsum>leftsum)
    			return rightsum;
    		else
    		{
    			return s;
    		}
    
    	}
    }
    int main() {
    	int a[max],num,k=0,sum;
    	
    	while (scanf("%d", &num) != EOF) {
    		k = 0;
    		while (k<num)
    		{
    			scanf("%d", &a[k]);
    			k++;
    		}
    		sum = minsum(a, 0, num-1);
    		printf("%d  %d  %d\n", sum,start,end);
    	}
    	return 0;
    }