yes we need to maintain an array that shows the real indexes before sorting and then loop on the elements and find the minimum index that appeared before a number in the sorted array and subtract it from it's index and find the maximum difference
On 6/12/10, divya jain <[email protected]> wrote: > i think we need to maintain an array of index as well such that while > subtracting smallest element from largest element of sorted array we need to > check if index of largest is greater than index of smallest. if no..then > this is not the solution.. > > On 12 June 2010 14:20, Modeling Expert <[email protected]> wrote: > >> 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]<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. > > -- 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.
