Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = &A[s_index] ;
end = &A[e_index];
result = 0; //! j - i
if ( *end > *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time < o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit <[email protected]> wrote:
> given an array A of n elements.
> for indexes j , i such that j>i
> maximize( j - i )
> such that A[j] - A [ i ]> 0 .
>
> Any Algorithm less than O(n^2) would do.
--
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.
