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 <[email protected]> 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 <[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]<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.
