求最大子序列和


问题：给定整数序列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+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

  1. Linux-C成长之路（一）：Linux下C编程概要
  2. Linux-C成长之路（二）：基本数据类型
  3. Linux-C成长之路（三）：基本IO函数操作
  4. Linux-C成长之路（四）：运算符
  5. Linux-C成长之路（五）：控制流
  6. Linux-C成长之路（六）：函数要义
  7. Linux-C成长之路（七）：数组与指针
  8. Linux-C成长之路（八）：存储类，动态内存
  9. Linux-C成长之路（九）：复合数据类型
  10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：

相关内容