One Solution for Largest span in array,I have checked it on many
inputs,according to me its working fine
void Large_Span(int * arr,int num_elem)
{
int j=1,k=0,i,prev_k=0;
for(i=1;i<num_elem;i++)
{
if(arr[i]>arr[i-1])
{
if((arr[j]-arr[k])<(arr[i]-arr[i-1]))
{
if(j<arr[i] && k<=arr[i-1])
{
j=i;
}
else if((j<arr[i] && k>arr[i-1])||(j>arr[i] && k>arr[i-1]))
{
j=i;
k=i-1;
}
}
else if(arr[k]>arr[i-1])
{
if(k<j)
{
prev_k=k;
k=i-1;
}
}
else if(arr[j]<arr[i])
j=i;
}
else
{
if(arr[k]>arr[i])
{
if(i>j)
{
prev_k=k;
k=i;
}
else
k=i;
}
}
}
if(k>j)
{
k=prev_k;
}
printf("arr[j]=%d,arr[k]=%d,j=%d,k=%d",arr[j],arr[k],j,k);
}
On Mon, Mar 22, 2010 at 8:28 AM, Manish <[email protected]> wrote:
> This does not look like a solution for the posted problem.
> This fails the test case {2, 7, 6, 0, 100}, where the answer should
> have been 4, for k=0 and j=4.
>
> Manish
>
> On Mar 20, 1:49 pm, saurabh gupta <[email protected]> wrote:
> > This may not be the optimal solution to
> > " Given an array of integers A[N], find the maximum value of (j-k) such
> > that A[k] <= A[j] & j>k.
> > I am looking for a solution with time complexity better than O(N^2)."
> >
> > this was in response to
> > "how u can solve it in o(n)"
> > and
> > "how to solve this in the claimed O(N) time."
> >
> >
> >
> > On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland <[email protected]>
> wrote:
> >
> > > On Mar 15, 10:07 am, saurabh gupta <[email protected]> wrote:
> > > > while you scan the array
> > > > maintain four indices plus two lengths
> > > > two indices and a length mark one sub-array - start,end, length
> > > > each such sub-array indicates a non-decreasing sequence,
> > > > call them S1 and S2.
> >
> > > > while one scans, S2 keeps track of incoming elements (curr sequence)
> > > > S1 keeps track of the maximum length (along with indices) so far
> (prev
> > > > sequence)
> > > > as one encounters an element which is less than the previous element,
> > > > this marks the end of S2,
> > > > S1 replaces S2 if len S2 > len S1 else S2 starts afresh from this new
> > > > element.
> >
> > > > In the end if len S2 > len S1 answer = S2
> > > > else answer = S1.
> >
> > > > PS: In the beginning and till one encounters a smaller element than
> the
> > > > prev one for the first time, S1 = S2
> >
> > > I agree that this is a nice algorthithm that solves the
> > > largest non decreasing sequence problem.
> > > However, I don't agree that this solves the problem
> > > originally posted.
> >
> > > Regards,
> >
> > > Ralph Boland
> >
> > > --
> > > 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]<algogeeks%[email protected]>
> <algogeeks%[email protected]<algogeeks%[email protected]>
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
> > Says he feels all alone in a threatening world where what lies ahead is
> > vague and uncertain. Doctor says "Treatment is simple. Great clown
> > Pagliacci is in town tonight. Go and see him. That should pick you up."
> Man
> > bursts into tears. Says "But, doctor...I am Pagliacci."
>
> --
> 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]<algogeeks%[email protected]>
> .
> 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 [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?hl=en.
