動態規劃算法--蠻力算法求最大子段和
來源：程序員人生 發布時間：2016-07-08 16:40:16 閱讀次數：2899次
問題： 給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當所給的整均為負數時定義子段和為0，依此定義，所求的最優值為： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，當（a[1],a[2],a[3],a[4],a[5],a[6]）=(⑵,11,⑷,13,⑸,⑵)時，最大子段和為20。
最大子段和是動態計劃中的1種。
當b[j⑴]>0時b[j]=b[j⑴]+a[j]，否則b[j]=a[j]。故b[j]的動態計劃遞歸式為:
b[j]=max(b[j⑴]+a[j],a[j])，1<=j<=n。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define NR(x) sizeof(x)/sizeof(x[0])
int MaxSum(int a[] , int n)
{
int sum = 0 ;
int b = 0 ;
int i ;
for(i = 1 ; i < n ; i++)
{
if(b > 0)
b = b + a[i] ;
else
b = a[i] ;
if(b > sum)
sum = b ;
}
return sum ;
}
int main(void)
{
int sum ;
int buf[] = { ⑵, 11, ⑷, 13, ⑸, ⑵};
sum = MaxSum(buf,NR(buf)) ;
printf("%d\n",sum);
return 0 ;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
