以int爲單位的最大總和的子序列

Question

給定一個整數數組，如何找到兩個索引i和j，以使子索引中的索引開始和結束的元素總和最大化，線性爲時間？

Answer 1

從我的programming pearls副本：

maxsofar = 0 
maxendinghere = 0 
for i = [0, n) 
    /* invariant: maxendinghere and maxsofar are accurate 
     are accurate for x[0..i-1] */ 
    maxendinghere = max(maxendinghere + x[i], 0) 
    maxsofar = max(maxsofar, maxendinghere) 

Answer 2

很簡單。假設你得到了數組a。首先，你計算陣列s，其中s[i] = a[0]+a[1]+...+a[i]。你可以做到這在線性時間：現在

s[0]=a[0]; 
for (i=1;i<N;i++) s[i]=s[i-1]+a[i]; 

，總和a[i]+a[i+1]+..+a[j]等於s[j]-s[i-1]。對於固定的j，要最大化這種差異的值，您應該在0..(j-1)範圍內找到最小的。

想象一下在數組中尋找最小值的常用算法。

min = x[0]; 
for (j=1; j<N; j++) 
    if (x[j] < min) 
    min = x[j]; 

您迭代，每個數組元素比較min ...但在每次迭代這min是數組，其中索引範圍是0..j最低值！這就是我們正在尋找的！

global_max = a[0]; 
max_i = max_j = 0; 
local_min_index = 0; 
for (j=1; j<N; j++){ 
    // here local_min is the lowest value of s[i], where 0<=i<j 
    if (s[j] - s[local_min_index] > global_max) { 
    global_max = s[j] - s[local_min_index] 
    //update indices 
    max_i = local_min_index + 1; 
    max_j = j; 
    } 
    //update local_min_index for next iteration 
    if (s[j]<local_min){ 
    local_min = s[j]; 
    // update indices 
    local_min_index = j; 
    } 
} 

Answer 3

這個Python代碼返回序列的邊界。根據原來的問題，i=bestlo，j=besthi-1。

# 
# given a sequence X of signed integers, 
# find a contiguous subsequence that has maximal sum. 
# return the lo and hi indices that bound the subsequence. 
# the subsequence is X[lo:hi] (exclusive of hi). 
# 
def max_subseq(X): 
    # 
    # initialize vars to establish invariants. 
    # 1: best subseq so far is [bestlo..besthi), and bestsum is its sum 
    # 2: cur subseq is [curlo..curhi), and cursum is its sum 
    # 
    bestlo,besthi,bestsum = 0,0,0 
    curlo,curhi,cursum = 0,0,0 
    for i in xrange(len(X)): 
     # extend current subseq and update vars 
     curhi = i+1 
     cursum += X[i] 
     if cursum <= 0: 
      # 
      # the current subseq went under water, 
      # so it can't be usefully extended. 
      # start fresh at next index. 
      # 
      curlo = curhi 
      cursum = 0 
     elif cursum > bestsum: 
      # adopt current subseq as the new best 
      bestlo,besthi,bestsum = curlo,curhi,cursum 

    return (bestlo,besthi) 

下面是這段代碼通過的一些doctest示例。

r''' 
    doctest examples: 
    >>> print max_subseq([]) 
    (0, 0) 
    >>> print max_subseq([10]) 
    (0, 1) 
    >>> print max_subseq([-1]) 
    (0, 0) 
    >>> print max_subseq(xrange(5)) 
    (1, 5) 
    >>> print max_subseq([-1, 1, -1]) 
    (1, 2) 
    >>> print max_subseq([-1, -1, 1, 1, -1, -1, 1, 2, -1]) 
    (6, 8) 
    >>> print max_subseq([-2, 11, -4, 13, -5, -2]) 
    (1, 4) 
    >>> print max_subseq([4, -3, 5, -2, -1, 2, 6,-4]) 
    (0, 7) 
    ''' 

Answer 4

你真正需要Kadane的算法變更該記住的下限和上限爲子陣列，這裏的C++代碼11：

#include <iostream> 
#include <vector> 

typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> SubSeq; 

SubSeq getMaxSubSeq(std::vector<int> &arr) { 
    SubSeq maxSequence{arr.begin(), arr.begin()}; 
    auto tmpBegin = arr.begin(); 
    int maxEndingHere = 0; 
    int maxSoFar = 0; 

    for(auto it = arr.begin(); it < arr.end(); ++it) { 
     int currentSum = maxEndingHere + *it; 

     if(currentSum > 0) { 
      if(maxEndingHere == 0) { 
       tmpBegin = it; 
      } 
      maxEndingHere = currentSum; 
     } else { 
      maxEndingHere = 0; 
     } 

     if(maxEndingHere > maxSoFar) { 
      maxSoFar = maxEndingHere; 
      maxSequence.first = tmpBegin; 
      maxSequence.second = it + 1; 
     } 
    } 

    return maxSequence; 
} 

int main() 
{ 
    std::vector<int> arr{-1, 2, 90, -50, 150, -300, 56, 12}; 

    auto seq = getMaxSubSeq(arr); 
    while(seq.first != seq.second) { 
     std::cout << *(seq.first) << " "; 
     ++(seq.first); 
    } 

    return 0; 
}