?

算法1：時間復雜度大并且不是很能理解，故不作展示

算法2：

?int MaxSubseqSum2(int A[], int N)
{
??? int ThisSum, MaxSum = 0;
??? int i, j, k;
??? for (i = 0; i<N; i++) //i是子列左端位置
??? {
??????? ThisSum = 0;??? //ThisSum是從A[i]到A[j]的子列和
??????? for (j = i; j<N; j++)??? //j是子列右端位置
??????? {
??????????? ThisSum += A[j];
??????????? if (ThisSum > MaxSum) //如果剛得到的這個子列和更大
??????????? {
??????????????? MaxSum = ThisSum; //則更新結果
??????????? }
??????????? } //j循環(huán)結束
??????? } //i循環(huán)結束
??? return MaxSum;
}

時間復雜度n*n

算法3：分而治之?

時間復雜度nlogn

算法4：在線處理 每次輸入一個值則立即計算

int MaxSubseqSum4(int A[], int N)
{
??? int ThisSum, MaxSum;
??? int i;
??? ThisSum = MaxSum = 0;
??? for (i=0; i < N; i++)
??? {
??????? ThisSum += A[i];
??????? if (ThisSum > MaxSum)
??????? {
??????????? MaxSum = ThisSum;
??????? }
??????? else if (ThisSum < 0)
??????? {
??????????? ThisSum = 0;
??????? }
??? }
??? return MaxSum;
}

?

轉載于:https://www.cnblogs.com/zhaoy-shine/p/10904329.html

總結

以上是生活随笔為你收集整理的数据结构：最大子序列和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。