Max subarray problem

原始问题

给一个数组a[0...n],假设a[s...t]是它的子数组,那么这个子数组的所有元素加起来最大是多少?

用数学语言形式化的描述就是:求0<=s<=t<=n 使得 a[s]+a[s+1] .... + a[t] 最大。

这是算法导论书上的一个经典例题。书上给出了怎么用Divide and Conque的方式求解,算法复杂度为O(nlgn)。但是它同时也说了,有更好的做法,能在O(n)复杂度内解决这个问题,并且把这个留成了课后习题。

这个问题具有最优子结构特性,可以采用类似于动态规划的方式自下而上的构造出来。假设原文题的最优解为OPT(n),下面探讨它与OPT(n-1)、a[n]的关系。貌似没有直接关系……

比如:

{0,0,10,10,0,8,20} 的最优解是sum{8,20} = 28

{0,0,10,10,0,8} 的最优解是sum{10,10} = 20

这两者之间没有直接的关系。

为了找到最优子结构特性,对上述问题稍稍做下变形。加一个限制条件,要求这个子数组的最右端必须是n。即

问题2:

给一个数组a[0...n],假设a[s...n]是它的子数组,那么这个子数组的所有元素加起来最大是多少?假设这个问题的最优解为OPT2(n)

分析问题2:

先考虑退化情况,假设原数组只有一个元素,那么它唯一的子数组就是它自己啦。这种情况下,

OPT2(0) = a[0];

然后考虑当有多个元素时,OPT2(i)与OPT2(i-1)的关系。

假设问题2中a[0...n]的的最优解是a[s...n]。假设从最优解中去掉a[n]后剩下的数组不为空,那么a[s...n-1]也应该是a[0...n-1]的最优解。

即当i>0时,有OPT2(i)= max(OPT2(i-1)+a[i] , a[i]);

所以,这个问题的解很容易通过一次遍历就能得到,算法复杂度为O(n)。

回头再看问题1,

假设问题1的最优解是子数组a[s...t] ,那么它的和应该等于OPT2(t)

所以问题1的最优解 OPT(n) = max{OPT2(i)| i=0,....n-1}

实际写代码,扫描一次即可。仿照std::max_element的代码写,但是多加一个临时变量。

一个用来保存问题1的答案,一个用来保存问题2的答案。

//[begin,end]
//[begin,end]. include the endIndex!
template  struct MaxSubArrayResult {
  size_t beginIndex;
  size_t endIndex;
  T sum;
  MaxSubArrayResult(size_t b, size_t e, T s)
      : beginIndex(b), endIndex(e), sum(s) {}
};

template 
MaxSubArrayResult calcMaxSubArray(const std::vector& input) {
  if (input.empty()) throw std::runtime_error("empty array");

  MaxSubArrayResult r(0, 0, input[0]);
  MaxSubArrayResult g(r);
  for (typename std::vector::size_type i = 1; i != input.size(); ++i) {
    if (g.sum > 0) {
      g.sum += input[i];
      g.endIndex++;
    } else {
      g.sum = input[i];
      g.beginIndex = i;
      g.endIndex = i;
    }
    if (r.sum < g.sum) r = g;
  }
  return r;
}

最大子数组积

与它关联的还有一个问题,假设不是求最大和,而是求最大积,该怎么办?考虑输入的数据有正有负,这时候我们需要保存两个值,一个是正的最大值,一个是负的最大值。

long calc(const std::vector<int>& nums){
   if(nums.empty())
        throw std::runtime_error("empty array");

    long m(nums[0]);
    long p1(m>0?m:0),p2(m<0?m:0);
    for(std::vector::const_iterator iter=nums.begin()+1;
      iter!=nums.end();++iter){
      const long i=*iter;
      if(i<0){
        long op2=p2;
        p2=p1==0?i:p1*i;
        p1=op2==0?0:(op2*i);
      } else if(i>0){
        p1=p1==0?i:p1*i;
        p2=p2==0?0:p2*i;
      } else {
        p1=p2=0;
      }
      m=std::max(m,p1);
    }
    return m;
}

两个子数组的最大和

问题:

给一个数组a[0...n],假设a[s...t]、a[u...v]是它的两个不相交的子数组,那么这两个子数组的所有元素加起来最大是多少?

这是我在去某互联网公司面试的时候遇到的题目。

解法是,先从右向左遍历一次,求最大子数组和。然后再从左向右遍历一次,结合上一次遍历得到的答案,计算出最优解。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥