问题描述：给定整数数组\(A{}_1,{A_2}, \cdots {A_N}\)，求\(\sum\limits_{k = i}^j {{A_k}} \)的最大值（如果所有整数为负数，则最大子序列的和为0）
输入：一个整数数组\(A{}_1,{A_2}, \cdots {A_N}\)
输出：最大子序列和的值
#include<iostream> using namespace std; int MaxSubsequenceSum(const int A[],int N) { int ThisSum,MaxSum,j; ThisSum=MaxSum=0; for(j=0;j<N;j++) { ThisSum+=A[j]; if(ThisSum>MaxSum) MaxSum=ThisSum; else if(ThisSum<0) ThisSum=0; } return MaxSum; } void main() { int A[]={4,-6,5,-2,-1,2,6,-2}; cout<<MaxSubsequenceSum(A,8); cout<<endl; //return 0; }
时间复杂度:\({\rm O}\left( N \right)\)
原文：http://www.cnblogs.com/riden/p/4564412.html