問題

已知一個長度為n的數(shù)組（允許負數(shù)）, 和一個整數(shù)k, 求：和小于k的最長連續(xù)子串？

例如:

k=184, A=[431, -15, 639, 342, -14, 565, -924, 635, 167, -70],

和小于184的最長子串為A[3..6]

寫個簡單測試先

require_relative '../longest_subarray_with_sum_less_than_k'

describe LongestSub do
  let(:array) {[431, -15, 639, 342, -14, 565, -924, 635, 167, -70]}
  let(:bound) {184}
  let(:result) {subject.longest(array,bound)}
  let(:ans) {array[3..6]}
  it "should compute the longest subarray whose sum <= bound" do
    expect(result).to eq ans
  end
end

分析

如果暴力枚舉起點和終點，復(fù)雜度為O(n^2)。能不能找到一些規(guī)律優(yōu)化呢？

Make hands dirty

單純考慮原數(shù)組好像找不到規(guī)律。

考慮前綴和，此時問題轉(zhuǎn)換為已知pre數(shù)組，求pre[j]-pre[i]<=k的距離最大(i,j)對.

由于有負數(shù)，pre數(shù)組沒有遞增規(guī)律。

第一個元素的右端點，就已經(jīng)難以確定了，必須從右到左掃描，直到差值<=k，有可能一個都不成功；而且，算好i后，算i＋1時好像還是要掃描所有之后的右端點。

于是考慮對pre排序, 然后可以用“雙指針”，不斷移動右指針直到>k，并一直保存當前最右下標。這樣需要復(fù)雜度O(nlogn)排序＋O(n) == O(nlogn)

Make it better

還有更好的方法嗎？有沒有什么規(guī)律，來排除一些值呢？

可以發(fā)現(xiàn)右端點中，如果j1<j2而且pre[j1]>=pre[j2]，那肯定不會選j1, 因為j2既比j1遠，求和時結(jié)果又比j1小。所以，可以從右到左掃描一遍，過濾掉不可能的右端點。

而且發(fā)現(xiàn)，這樣過濾后的右端點在pre上是遞增的，就可以用“雙指針”求了。

復(fù)雜度 = O(n)過濾 + O(n)掃描 ＝ O(n)

代碼：

class LongestSub
  def longest(arr,bound)
    reset(arr,bound)
    l,r = [(0...size),poss_r].map(&:to_enum)
    loop { update(l,r) }
    arr[@longest_range]
  end

  def update(l, r)
    i,j = [l,r].map(&:peek)
    if i<=j && presum(j,i)<=bound
      @longest_range = [@longest_range, (i..j)].max_by(&:size)
      r.next
    else
      l.next
    end
  end

private
  attr_reader :arr, :bound
  def reset(arr,bound)
    @arr,@bound=[arr,bound]
    @poss_r = @pre  = nil
    @longest_range = (0...0)
  end
  def size; arr.size end
  def pre
    @pre ||= arr.reduce([0]){|res,v| res << res.last+v}
  end
  def presum(j,i=0)
    pre[j+1] - pre[i]
  end
  def poss_r
    @poss_r ||= (0...size).reverse_each.reduce([]) do |res,i|
      res.unshift(i) unless res.first && presum(i) >= presum(res.first)
      res
    end
  end
end