These are the steps for the O(n^2) solution
n=length of A
for each subarray A[i,j] where j>i
min=min(A[i,j])
max=max(A[i,j])
if(max - min==size (A[i,j]) print A[i,j]
min[A[i,j]]=min( A[j], min(A[i,j-1])
similar one for max
Note:
A[i,j] = A[i],A[i+1]....A[j]
I was wondering how to do the same problem in O(nlogn)
-- Vinod
On Wed, Dec 2, 2009 at 11:48 AM, ranjmis <ranj...@gmail.com> wrote:
> Vinod. Can you please mention steps for the O(n^2) solution that you
> have thought of.
>
> On Dec 2, 9:50 am, Vinoth Kumar <vinoth.ratna.ku...@gmail.com> wrote:
> > No need for the code guys.
> > Can u give me a algo or pseudo code for this problem.
> > I can think of a soln of O(n^2) but i need a algo for O(nlogn)
> >
> >
> >
> > On Wed, Dec 2, 2009 at 2:06 AM, NickLarsen <fodylar...@gmail.com> wrote:
> > > That doesn't quite get it, try the input [ 7 3 4 2 1 6 5 8] and your
> > > idea would miss [3 4 2]
> >
> > > On Dec 1, 10:10 am, sharad kumar <aryansmit3...@gmail.com> wrote:
> > > > find out the subseq which are consecttive
> > > > concatenate them at each level to get the entire set.
> >
> > > > On Tue, Dec 1, 2009 at 12:03 PM, Vinoth Kumar
> > > > <vinoth.ratna.ku...@gmail.com>wrote:
> >
> > > > > Given an array A which holds a permutation of 1,2,...,n. A
> sub-block A
> > > > > [i..j] of an array A
> > > > > is called a valid block if all the numbers appearing in A[i..j] are
> > > > > consecutive numbers (may not be in order.
> >
> > > > > Given an array A= [ 7 3 4 1 2 6 5 8]
> > > > > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5],
> [7
> > > > > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]
> >
> > > > > Give an O( n log n) algorithm to count the number of valid blocks.
> >
> > > > > -- Vinod
> >
> > > > > --
> >
> > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algoge...@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > <algogeeks%2bunsubscr...@googlegroups .com>
> > > > > .
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> >
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@googlegroups.com>
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Cheers,
> > Vinod
>
> --
>
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
