@Satya: I don't think what you have coded will work.. though i have not read the whole code.
Don't you think a simple divide and conquer scheme would work...(almost like the mergesort) -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 12, 2010 at 9:06 PM, Satya <[email protected]> wrote: > This problem seems to be finding the maxdiff in an array. > > int maxdiff ( int A[], int n ) { > // write your code here > int max_diff = A[1] - A[0]; > int min_element = A[0]; > int i; > for(i = 1; i < n; i++) > { > if(A[i] - min_element > max_diff) > max_diff = A[i] - min_element; > if(A[i] < min_element) > min_element = A[i]; > } > if(max_diff < 0) > max_diff = 0; > return max_diff; > } > > ......... > Satya > > > > On Sat, Jun 12, 2010 at 3:18 PM, 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]<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]<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.
