i meant make an array of indexes.. index[]={0,1...,n-1}
now sort the original array and move the elements of index array
accordingly..
now follow modelling expert's algo nd while taking largest-smallest check if
the index of largest in index array > index of smallest in index array.
On 13 June 2010 08:38, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote:
> @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<http://www.cse.iitb.ac.in/%7Erohitfeb14>
>
>
>
> On Sat, Jun 12, 2010 at 9:06 PM, Satya <satya...@gmail.com> 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 <sweetdivya....@gmail.com>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 <cs.modelingexp...@gmail.com>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 <amitjaspal...@gmail.com> 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 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<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>
>> .
>> 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>
> .
> 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.
