最大连续子序列和算法

原创
2021/11/28 13:32
阅读数 624

最大连续子序列和算法:从结果反推,找出前后依赖的相关性,去相关和冗余,来降低复杂度,复杂度为O(n), 与Sunday字符串匹配算法有点类似。

序列: a[i], (i =0,...n-1)

假如最大连续子序列和是a[k]到a[m-1](m-1> k), 那么a[k]到a[m-1]一定是a[0]到a[m-1]中最大连续子序列和

subSum[i-1]代表以a[i-1]为结尾的最大连续子序列和,那么

当subSum[i-1]>0时,以a[i]为结尾的最大连续子序列和为subSum[i]=subSum[i-1]+a[i];

否则,subSum[i-1]不会对后面的a[i]做增加的贡献,直接跳过subSum[i-1],重新开始计算新序列和,subSum[i]=a[i];

每次不断保存最大连续子序列和

 

C语言实现:

#include <stdio.h>

int maxSubSum(int iArr[], int iNum)
{
    int i, iMaxSum = 0, iMaxSubSum = 0;
    
    if (iNum < 1)
        return 0;
    else if (iNum == 1)
        return iArr[0];
    
    iMaxSubSum = iArr[0];
    iMaxSum = iArr[0];
    
    for (i = 1; i < iNum; ++i)
    {
        iMaxSubSum += iArr[i] ;
        if(iMaxSubSum > 0)
        {
            if(iMaxSubSum > iMaxSum)
                iMaxSum = iMaxSubSum;
        }
        else
        {
            iMaxSubSum = 0;
        }
    }
    
    return iMaxSum;
}

int main(void)
{
    int iArr[] = {-2, 1,-3, 4, -1, 2, 1,-5, 4, 1, -3, 4, -3, 4};
    int iArrLen = sizeof(iArr)/sizeof(iArr[0]);

    printf("maxSubSum = %d\n", maxSubSum(iArr, iArrLen));
    return 0;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部