7 ms·

Did you provide the O(n) solution or O(n3) brute force solution? I think that's the important bit.

• pjscott 7y ago
  Nit: The brute-force solution for the one-dimensional case is O(n^2), not O(n^3).
  • olooney 7y ago
    According to the Wikipedia page[1], the brute force solution is O(n^3) for the one-dimensional case. They don't give an algorithm, but the obvious pseudo-code is: highest_total = 0 for all i from 0 to length-1: for all j from i+1 to length-1: total = 0 for all k from i to j-1: total += data[k] highest_total = max(total, highest_total) return highest_total It takes three nested loops, with the third being the sum from i to j. This is obviously a very naive algorithm, but that's why it's called brute force. According to Wikipedia, Grenander apparently improved this to O(n^2), and then Jay Kadane came up with the first O(n) solution. For the 2D case, brute force is actually O(n^6). [1]: https://en.wikipedia.org/wiki/Maximum_subarray_problem https://en.wikipedia.org/wiki/Maximum_subarray_problem
    • pjscott 7y ago
      Huh! That's a bit more brutishly forceful than I was expecting, and I concede the point. It hadn't occurred to me to stick that innermost loop in there rather than keeping a running sum in the second loop.
    • B4TMAN 7y ago
      This problem gets more interesting when they ask you to remember the indices of that particular subarray. Wikipedia explains that scenario well.
  • elihu 7y ago
    The brute force solution that seems most obvious to me is to pick a starting index and an ending index out of all possible indexes such that start < end, and calculate the sum of that sub-array (keeping the biggest result). This is O(N^3) because iterating over index pairs is O(N^2) and doing the sum is O(N).
  • zucker42 7y ago
    Brute is choosing every index pair (n^2) and calculating the sun of their subarray (n). With prefix sums you can get to n^2.
• olooney 7y ago
  O(n). Faster than 75% of accepted solutions. :)