動态規劃 - 最大子段和

問題描述

給定 n 個整數組成的序列 a[1],a[2],a[3],……,a[n] ，求該序列如 a[i],a[i+1],a[i+2],……,a[j] 的連續子段和的最大值。

    例如，在序列 -2,11,-4,13,-5,-2 中，最大子段和為 20 。
           

分析

記 b[j]=max(a[i]+a[i+1]+……+a[j]) ，其中 1<=i<=n,1<=j<=n ，則所求最大子段和為 max=max(b[j]),1<=j<=n 。

    顯然，該問題滿足 無後效性 。在計算 b[j] 時，我們需要考慮 b[j-1] ,即考慮之前序列的最大子段和的正負情況：

        當 b[j-1]>0 時，有 b[j]=b[j-1]+a[j] ；
        當 b[j-1]<=0 時，有 b[j]=a[j] 。
           

實作

#include<stdio.h>
int main(void){
    int count,a[]; //定義測試數組以及其大小
    int b[]; //定義子段和數組
    int max;//含 count 項序列的最大子段和
    scanf("%d",&count);
    for(int i=;i<count;i++){
        scanf("%d",&a[i]);
    }
    b[]=a[];
    max=b[];
    for(int i=;i<count;i++){
        if(b[i-]>)
            b[i]=b[i-]+a[i];
        else
            b[i]=a[i];
        if(b[i]>max)
            max=b[i];
    }
    printf("%d",max);
    return ;
}
           

#include<stdio.h>

int max(int num1,int num2);
int maxSum(int data[],int count);

int main(void){
    int count,data[]; 
    scanf("%d",&count);
    for(int i=;i<count;i++){
        scanf("%d",&data[i]);
    }
    printf("%d",maxSum(data,count));
    return ;
}

int max(int num1,int num2){
    return num1<num2?num2:num1;
}

int maxSum(int data[],int count){
    int currentSum=data[];
    int ans=currentSum;
    for(int i=;i<count;i++){
        currentSum=max(currentSum+data[i],data[i]);
        ans=max(ans,currentSum);
        printf("%d",ans);
    }
    return ans;
}