b***y
发帖数: 2799 | 1 ☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Wed Jul 16 16:32:01 2008) 提到:
Find the sequence of consecutive numbers that add up to a maximum (or
highest) total within the array. Write a function to find the sum and also
the start and end positions of the sequence. The solution should be of O(N)
time complexity.
For example if the array is (0, -1, 2, -1, 3, -1, 0), maximum sum would be 4
(= 2 + -1 + 3).
I can only figure out way of O(N^2), but how can it be done with O(N)?
☆─── |
|
