On May 12, 11:58 am, Jagadish M <[email protected]> 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 := 0
aa := 1
for bb := 2 to n do
diff = mod(arr[bb] - arr[bb-1])
if diff >=M then
if curr=0 OR (arr[bb]- arr[bb-1])*(arr[bb-1] - arr[bb-2])
<0 then
curr:= curr + diff
else
curr:= diff
aa := bb-1
endif
if curr > max then
(max, a, b) := (curr, aa, bb)
endif
else
curr := 0
aa := bb
endif
endfor
return (max, a, b)
end
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
