[algogeeks] Re: Zig-zag subsequence

2009-05-14 Thread p0r$h
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

[algogeeks] Re: Zig-zag subsequence

2009-05-13 Thread Jagadish M
> > > 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

[algogeeks] Re: Zig-zag subsequence

2009-05-09 Thread Raghav Kumar Gautam
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