歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

求最大子序列和

問題:給定整數序列S[0],S[1],... S[N-1],子序列和是指S[i]+S[i+1]+...+S[j-2]+S[j-1],其中i,j, 0<= i <= j <= N-1,求所有這樣的子序列和的最大值,即最大子序列和。

方法一:枚舉法 O(N^2)

求出所有的子序列和,取其最大值。算法復雜度為O(N^2)。

int maxSubSeq1(int a[], int len)
{
    int maxSum;
    int i, j;
 
    if (len <= 0) return MIN_INT; /* MIN_INT可取足夠小的整數 */
 
    maxSum = a[0];
    for (i = 0; i < len; ++i) {
        int thisSum = 0;
        for (j = i; j < len; ++j) {
            thisSum += a[j];
            maxSum = (thisSum > maxSum ? thisSum : maxSum);
        }
    }
    return maxSum;
}

方法二:動態規劃 O(N)

這個問題可以采用動態規劃來解答。假設對N個數的序列S[0…N-1],最大子序列和為F(N),令M(N)為包含S[N-1]的最大子序列和。當已求得F(N-1)時,考慮S[N-1],最大子序列可能有以下兩種情況,一是包括S[N-1],一是不包括S[N-1]。不包括S[N-1]時,F(N) = F(N-1);包括S[N-1]時,F(N) = M(N)。

所以 F(N) = max{ F(N-1), M(N) }。

現在的問題就剩下求M(N)了,而 M(N) = max{ M(N-1)+S[N-1], S[N-1] }

即,M(N) = (M(N) > 0 ? (M(N) + S[N-1]) : S[N-1]);

算法復雜度為O(N)

int maxSubSeq2(int a[], int len)
{
    int maxSum, lastMaxSum;
    int i;
 
    if (len < 0)  reutrn MIN_INT; /* MIN_INT可取足夠小的整數 */
    maxSum = a[0];
    lastMaxSum = a[0];
    for (i = 1; i < len; ++i) {
        lastMaxSum = (lastMaxSum > 0 ? lastMaxSum + a[i] : a[i]);
        maxSum = (lastMaxSum > maxSum ? lastMaxSum : maxSum);
    }
    return maxSum;
}

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將C語言梳理一下,分布在以下10個章節中:

  1. Linux-C成長之路(一):Linux下C編程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
  2. Linux-C成長之路(二):基本數據類型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
  3. Linux-C成長之路(三):基本IO函數操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
  4. Linux-C成長之路(四):運算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
  5. Linux-C成長之路(五):控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
  6. Linux-C成長之路(六):函數要義 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
  7. Linux-C成長之路(七):數組與指針 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
  8. Linux-C成長之路(八):存儲類,動態內存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
  9. Linux-C成長之路(九):復合數據類型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
  10. Linux-C成長之路(十):其他高級議題

Copyright © Linux教程網 All Rights Reserved