@topcoder:
If i understood it correctly, what you are trying to do here, is
basically check whether A[i] > A[j], then take the length of the max
sequence that is zigzag ending at A[j] with the last difference being
negative i.e. A[j] - A[previous index in zig-zag seq] is negative,
otherwise vice v
int LIDS ( vector a , int n ){
int s[51][2];
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < 2 ; j++)
s[i][j] = 1;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < i ; j++){
if( a[i] != a[j] ){
s[i][a[i]>a[j]] = max(s[j][a[i]a[j
bit alteration to the max width problem, thats it nothing else.
Thank you,
Sid.
On Sun, Aug 28, 2011 at 11:07 PM, siddharam suresh
wrote:
> if its only printing the values then
>
>
>
> int get_height(node temp)
> {
> if(temp!=NULL)
> {
>
> return(get_height(temp->L)>get_height(temp->R)?(get_h
if its only printing the values then
int get_height(node temp)
{
if(temp!=NULL)
{
return(get_height(temp->L)>get_height(temp->R)?(get_height(temp->L)+1):(get_height(temp->R)+1));
}
return 0;
}
void get_width(node temp, int level,int direction)
{
if(temp==NULL) return 0;
if(level==1) {pri
@ Kartikeyan:
If you use normal queue implementation how you are going to print reverse???
(From ptr2 to ptr1)...If you are implementing queue in an array, then your
solution can be feasible..
If not in array, you must modify your queue DS to include pointers to
previous elements.
Or you can do th
Liao, your solution will generate the required manner. However, can
you try to do the same by using some bool value and a single stack/
queue? Let bool value decide whether you want to insert right to left
or left to right. Haven't tried myself but think that should work.
Karthik, never did i ment
dp[i][0] denotes the index of last element of MAX -ve(1st diff is -ve)
sub sequence ending at i
dp[i][2] denotes the length of this sub sequence
dp[i][1] denotes the index of last element of MAX +ve(1st diff is -ve)
sub sequence ending at i
d[[i][3] denotes the length of this sub sequence
-initial
No , actually it's not ... it's O(n^2) , I misunderstood the
"subsequence" thing , it could be discontinuous .. we , then need to
find the maximum of dp[l] ...
the second term makes sure that the sign of the two quantities is
alternating i.e. positive or negative !
On Jan 29, 11:06 am, nishaanth
@above...can you please enlighten me about the second term in the dp
expression
And are you sure its O(n) ?
On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava <
richi.sankalp1...@gmail.com> wrote:
> This can be done in O(n) very easily , similar to Longest increasing
> subsequence
>
> Solution :
This can be done in O(n) very easily , similar to Longest increasing
subsequence
Solution :-
dp[l]= maximum length of the zigzag sequence upto the length l
//At any position , the particular number in the array can either
extend the zigzag sequence containing the last element or it can start
one
well I found it as it Can be Done in O(n). but with additional space
O(n)
here program is written in Java
public class ZigZag
{
public int longestZigZag(int[] sequence)
{
if (sequence.length==1) return 1;
if (sequence.length==2) return 2;
int[] diff = new int[sequence.length-1];
fo
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
14 matches
Mail list logo
