最大子段和 or 最大子序和

标签：最大 nums 子段 负数 数组 序列 子序

老生常谈序列和串的区别

最长公共子序列和最长公共子串区别

最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别：

子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。

子串和子段，都要求连续

求最大子段（子序）和

意思就是，给定一个整数数组nums[]，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组[4,-1,2,1]的和最大，为6。

设有这样的一个数组:

{-2,-1,3,5,10,-2-,1,2,5,-2}

我们可以思考一下，最大的连续元素和，他们的头和尾部不会带有让他们的和减小的负数

也就是说，当有前几个元素的和为负数的时候，后面的元素运算必定不会带上前面这个和为负数的子段

所以我们可以建立一个辅助数组MAX，存储他们的局部最优解

 

 

第一个开始，他自己本身就是自己的局部最优解，填入他自己

 

 下一个元素判断，他的前面的最优解是否为负数，是的话就不用加上，填入自己本身，前面不是负数的话就把前最优解加上自己填入

这里的第二个是-1 ，前面是-2 ，是负数，填入自己就行

 

 经过运算最后我们可以得到

 

 解下来在里面找到最大值即可，最大值就是他们的子段最大和

状态转移方程代码

 通过以上的分解后，我们可以得到这样一个状态转移方程

function maxSubArray ( nums: number[] ) : number {
    for (let i = 1; i < nums. length; i++) {
        if(nums[i一1]>0){
            nums[i] = nums[i] + nums[i-1] ;
        }
    }
        return Math.max( ...nums ) ;
};
                

返回序列信息

由于我们知道了最大sum值就是他的最长值

所以最大sum值就是得到子段的最后一个元素

我们从最后一个开始，往前遍历到负数的局部最优解，就是序列开始的前一个了

这样就能知道序列的开头和结尾了

代码

# include<stdio.h>
 
int main(){
    int n;
    scanf("%d", &n);
    int a[n]={0};
    for(int i = 0;i<n;i++){
        scanf("%d", &a[i]);
    }
    int max = 0;  // 最大值
    int tem = 0;  // 段值
    for(int i=0;i<n;i++){
        if(tem>0)  // 前面一段值大于0
            tem+=a[i];
        else{  // 前面一段值小于0
            tem=a[i];  // 抛弃前面的段值，更新段值
        }
        if(tem>max){  // 更新最大值
            max=tem;
        }
    }
    printf("%d", max);
    return 0
}

 

标签：最大,nums,子段,负数,数组,序列,子序
From： https://www.cnblogs.com/kuailest/p/16882255.html