When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

el3el2's blog

By el3el2, history, 8 years ago, In English

I am trying to find an O(n) solution to this problem:

Given an array, find the subarray with the sum closest to 0.

An O(nlogn) solution is kinda straightforward, but I have read this problem in a textbook in a context suggesting there's a O(n) solution. Any help?

  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

i don't know but looks like it's a variant of kadane algorithm

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not as far as my thought process could go. A variation of Kadane algorithm can be used to find the minimum sum; but could not apply that to a specific sum.

    The simplest form of this problem I could find is finding the closest two elements in an array (the prefix sums in this problem).