On May 12, 11:58 am, Jagadish M wrote:
> > > Try dynamic programming. Complexity of the algorithm would be O(n^3).
>
> Won't it just be O(n^2)?
Using the variation of kadane's algorithm, here is an O(n) run time
algorithm.
zigzag(arr[1..n], M)
begin
(max, a, b) := (-INFINITY, 0, 0)
curr
>
> > Try dynamic programming. Complexity of the algorithm would be O(n^3).
>
Won't it just be O(n^2)?
Suppose A is the input.
Let F(i,+) denote the maximum sum you can accumulate with the sequence
ending at A[i] and the last difference being positive.
Define F(i,-) accordingly. Computing each F
Vladimir Reshetnikov
writes:
> Please help me to write the following algorithm:
> Call a sequence of integers a zig-zag sequence if the differences between
> successive numbers strictly alternate between positive and negative (for
> example,
> 5, 7,3,9,-1,4,3,6,0). The first difference may be
