CareerCup

A Simple and cleaner solution. No need to check for index j > i etc.

private void MaxDiff(int[] a)
       {
           int min = a[0]; // assume first element as minimum
           int maxdiff = 0;
           int posi = -1, posj = -1, minpos = 0;

           for (int i = 1; i < a.Length; i++)
           {
               if (a[i] < min)
               {
                   min = a[i];
                   minpos = i;
               }
               else
               {
                   int diff = a[i] - min;
                   if (diff > maxdiff)
                   {
                       maxdiff = diff;
                       posi = minpos;
                       posj = i;
                   }
               }
           }
           Console.WriteLine("i={0}, j={1}",posi,posj);
       }

The solution is quite simple, one pass:

Start checking from the beginning of the array. Initially there are no min/max values stored.
If the current element is smaller than the stored min, replace the stored min with current element and clear stored max (the stored max is no longer valid for this current min).

If the current item is larger than the current max and larger than the stored min, store it as a max. If this currently stored min/max pair is bigger difference than the previous, overwrite it (this will be the returned value).

To make it visible:

2     1     4     100     -5
Min          2     1     1      1         -5
Max         inv   inv   4      100    inv

When you hit 100, you see the current Min/Max pair is bigger than the previous (1/4) so you store it as the return value. The last one, -5 does not have a valid pair, so you return 1/100.

Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i<N;++i) B[i] = min(A[i],B[i-1]);
2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(j<N) do {
while(B[i] < C[j] && j<N) j=j+1;
max_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}
===============
Each step is O(N). I am sure it can be done some more elegant way though...

A[8] = {20,30,2,11,12,10,1,4};
1) B[8] = {20,20,2,2 ,2 ,2 ,1,1};
2) C[8] = {30,30,12,12,12,10,4,4};
3) the loop while(j<8) stops with max_i_j = 7-2=5 on i=2,j=7

Consider the left point of those pair (i, j) first.
Suppose i < k and A[i] <= A[k]. Then for any k < j and A[k] < A[j], i must be better than k, i.e. k is useless as a "left point"

Now scan from the left of array A, to find all the left point candidates, they must be:
A[i_1] > A[i_2] > A[i_3] > ... > A[i_m], here 1 = i_1 < i_2 < ... < i_m <=n

Keeping a pointer whose initial value is ptr = m,
Second scan from the right side, for every j:

if (i_ptr > j) ptr = ptr - 1;
while (ptr > 1) and (A[i_ptr] >= A[j]) ptr = ptr - 1;
while (ptr > 1) and (A[i_(ptr-1)] < A[j]) ptr = ptr - 1;
checking pair(i_ptr, j)

Finally, we get the maximum (j - i) in O(n) time.

/*
How about this solution?
Suppose we have an array, A[0 ..... n]

if (A[n] > A[0]) then return n;
else return Max(findMax(A[0 ... n-1]), findMax(A[1 ... n]))

So it is a dynamic programming problem.
The worst case is time complexity is O(n^2)
*/

int DPRecord[N][N]; // each cell should be initialized by -1

int findMax(int *A, int i_start, int i_end) {
if (i_end <= i_start) return -1;
if (DPRecord[i_end][i_start] != -1) return DPRecord[i_end][i_start];

if (A[i_end] > A[i_start]) {
DPRecord[i_end][i_start] = A[i_end] - A[i_start];
}
else {
int max1 = findMax(A, i_start+1, i_end);
int max2 = findMax(A, i_start, i_end-1);
DPRecord[i_end][i_start] = max1 > max2 ? max1 : max2;
}

return DPRecord[i_end][i_start];
}

int main (int argc, char *argv[]) {
int answer = findMax(A, 0, length(A));
if (answer == -1) cout << "NO ANSWER!!" << endl; // this array looks like: 5 4 3 2 1 -> no answer!!
else cout << answer<< endl;
}

Idea would be to store the positions (not values) in stack as the value is increasing. Any time value decreases, go through the stack and remove all values higher than current.
So at any point of time, we will have only increasing positions in the stack.
This idea was used to calculate max area under histogram :)

stack s;
s.push(0); cur = arr[0]; int maxdist = 0;
for(int i=1; i< length; i++)
{
   if(arr[i] > cur)
  {
     s.push(i); //push position
      cur = arr[i];
   }
   else
   {
     int cnt = 0;
     while(arr[stack.pop()] > arr[i])
     {
        cnt++;
     }
     //Now push arr[i]
     stack.push(i);
     if(maxdist < cnt)
       maxdist = cnt;
   }
} //end for loop.

//There are items left in stack. Get the difference is positions to see if we have a max
int top = stack.pop(); while(!empty){bottom = stack.pop()};
if((top - bottom) > maxdist) maxdist = top-bottom;

return maxdist;

if it were asked to find out minimum j-i such that A[i] < A[j], it could be solved using stack in O(n) time. But, I doubt for max j-i such algorithm ever exists.

Seems all previous CORRECT solutions takes O(n^2) time - which is trivial. Any idea of O(n logn) solution there?

This can be solved in O(n) time by using dynamic programing. This is similar to the classic when to sell your share problem. You use the iterative solution of
max[n]=max(0, max(n-1)+(A[j]-A[j-1])). This would give you the differences of each particular day for diff choices of i and j. In a single pass of O(n) you can find the maximum, which is the answer we are looking for. coding this should not be difficult

This can be done in O(n).. Here's how..
Keep two pointers, left and right. Check values pointed by left and right pointers. If the value pointed by right is greater than that pointed by i, store j-i and increment i. Otherwise, decrement j till such a condition occurs. Now, say i has been incremented. If the value pointed by this new i is greater than the one previously pointed by it, simply increment i as in this case j-i can never exceed previously computed j-i. If the value is smaller, then search from current j to the last element.. If such an element is found, update j-i.

void longestContinuousIncrSeq(int* a, int size) {
        int maxstart = 0;
        int max = 1;
        int start = 0;
        for (int i = 1; i < size; i++) {
            if (a[i] > a[i - 1]) {
                if (i - start + 1 > max) {
                    max = i - start + 1;
                   maxstart = start;
                }
           } else {
                start = i;
            }
        }
        cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;
       for (int i = 0; i < max; i++) {
            cout << a[maxstart + i] << " ";
        }
        cout << endl;
    }

@celicom The logic given by you seems to be working. Do you have any mathematical proof or reference site/book for this logic?

can sb explain the question with sample i/p & o/p ..

<pre lang="" line="1" title="CodeMonkey29338" class="run-this">int main() {
int arr[] = {21, 25, 1, 17, 16, 13}
int start = 0, end = 0;
solve(arr, 6, start, end);

cout << "The start point is " << start << " and the end point is " << end
<< endl;
return 0;
}

int solve(int arr[], int len, int& start, int& end) {

int min = 0;
int maxDiff = INT_MIN;

for (int i = 0; i < len; i++) {

if (arr[i] < arr[min])
min = i;

if ((i - min) > maxDiff) {

maxDiff = i - min;
start = min;
end = i;
}
}
return;
}</pre><pre title="CodeMonkey29338" input="yes">by slimboy
</pre>

@celicom:this is not a o(n) approach.

Here is the code. Please correct me if any mistake

void FindMaxDiff(int arr[], int arr_size)
{
int i, first, second;
int diff = 0;
/* There should be atleast two elements*/
if(arr_size < 2)
{
printf(" Invalid Input ");
return;
}
first = second = 0;
for(i = 0; i < arr_size ; i ++)
{
/*If current element is smaller than first then update both first and second */
if(arr[i] > first)
{
second = first;
first = arr[i];
if(diff < (first-second))
diff = (first-second);
}
/* If arr[i] is in between first and second then update second */
else if (arr[i] > second)
{
second = arr[i];
}
}
Printf(“ xxxx “);
}

@sidhartha,thanks for quick reply
Can you check you above code on input 2,1,4,100,-5
value of max difference,diff should be 99(100-1)
but your code after loop iteration will give 96.

/*
one unsorted array is given.Find out the index i and j ,j> i for which a[j] - a[i] is maximum.perform in linear time complexity
*/

bool findLargestDiff(int data[], int size, int &low, int &high)
{
	int tmpLow = 0, tmpHigh = 1;
	
	if(size < 2)
		return false;

	int low = 0, high = 1;
	
	if(size == 2)
	{
		return true;
	}
	
	while(tmpLow < size - 1 && tmpHigh < size)
	{
		if(data[tmpLow] > data[tmpLow+1])  //we try to find the lowest point at first
		{
			tmpLow++;
			if(tmpHigh <= tmpLow) tmpHigh = tmpLow + 1;   //j > i is a requrement 
			
			if(data[tmpHigh] - data[tmpLow] > data[high] - data[low])  //cover {-10, -5, -3} scenario
			{
				low = tmpLow;
				high = tmpHigh;
			}
		}
		else  //the next is biggest than the tmpLow
		{
			while(tmpHigh < size)
			{
				if(data[tmpHigh] > data[tmpLow])
				{
					if(data[tmpHigh] - data[tmpLow] > data[high] - data[low])
					{
						low = tmpLow;
						high = tmpHigh;
					}
					tmpHigh++;
				}
				else  //find a new low 
				{
					tmpLow = tmpHigh;
					tmpHigh++;
					break;
				}
			}
		}
	}
	
	return true;
}

1. Find min and max element in the array.
2. The diff between them is the max diff.

For understanding the solution better i'll the algorithm in two passes at max (still order is O(n)):
In the first pass find out the maximum and minimum elements. If the index of maximum is greater than that of minimum then the problem is solved. Otherwise find:
let min,max be the found minimum and maximum elements respectively.
maximum(diff(minium element that is left to max,max),diff(min,maximum element that is right to min))

If we manage the variables properly we can do it in one pass :)

Eg: 5, 15, 2, 10, 20, 1, 17, 0, 8, 16
Apparently the required indexes are 2,4 (max difference =18)

Now using algo,
minimum element = 0
maximum element = 20
but index of 0 > index of 20
now minimum element left of 20 is 2, difference1 = 18
maximum element right of 0 is 16, difference2 = 16
maximum(difference1, difference2) = 18

Order is O(n) and if we manage variables properly, we can do it in one pass

'i' will iterate from 0 to n-2 and 'j' from 1 to n-1.
update iLoc and jLoc accordingly. jLoc will contain the largest element in the array and iLoc has smallest. so the difference will be maximum. For the condition i<j we should check if jLoc is greater the 'i' in the iteration.

//takes array as argument and returns an array with iLoc and jLoc
compute smalliLargej(a)
{
   int iLoc = 0;
   int jLoc = 1;
   int smallestI = a[0];
   int largestJ = a[1];
   for(int i = 0, j = 1;j < n;i++,j++)
   {
       if(a[j] > largestJ)
           {
                jLoc = j;
                largestJ = a[j];
           }
       if(a[i] < smallestI && i < jLoc)
          {
                iLoc = i;
                smallestI = a[i];
           }
   }
   int[] temp = {iLoc,jLoc}
   return temp;
}

//A c# version

void FindMaxDiff(int[] arr, out indx1, out indx2)
{
int len = arr.Length;
int i,j, max, min;
min = arr[0];max = 0;
for (i=0,j=1;j<len;i++,j++)
{
if(arr[i]<arr[j])
{
if(arr[i]<min)
{
min = arr[i];
indx1 = i;
}
if(arr[j]>max)
{
max = arr[j];
indx2 = j;
}
}
}
}

j is always greater than i, since we do not check the conditions for max being i and the rest is finding the max and min simultaneously. 3 comparisons for every 2 values better than 4 comparisons. O(n)
Please let me know if there are errors here

This can be done in 3 pases
1 pass) Find the minimum till that index for each index and store it an array A
2 pass) Find the maximum till that index for each index but traverse the array in reverse order and store it an array B
3 pass) Find the difference B[i] - A[i] at each index you will get the max difference and from that the indexes

example
input : 5 15 3 10 20 1 19 0 8 16

A : 5 5 3 3 3 1 1 0 0 0
B : 20 20 20 20 20 19 19 16 16 16
diff: -----------17 17 18 18(max) 16 ---------

find indices of 19 and 1 linear solution and simple though there could be better ;)

isn't it the same problem as having the max profit in share price movements of a given date?

Question says "perform in linear time complexity" .. I have a doubt cant we use two for loops?

By the way.. Can some one review this solution:

int a[4] = {2,3,1,4,5,1,6,2,3,4};
int n=10;
int ti, tj, maxj, mini, i, j;
i=n-1;j=n-1;
mini=0; maxj=n-1; ti=0;tj=0;
for(int k=0, l=n-1; k<n; k++,l--)
{
if(a[k]>=a[tj])
{
tj=k; ti=mini;
}
else if(a[k]<a[mini]) mini=k;

if(a[l]<=a[i])
{
i=l; j=maxj;
}
else if(a[l]>a[maxj]) maxj=l;
}

if (a[tj]-a[ti] > a[j]-a[i]){ i = ti; j=tj;}


//- -- - -- -- here we re traversing from left to right...
finding the largest a[k] and replacing j=k; if current a[i] > some k which we have already passed through then i== that minimum;

at the same time we are going right to left..
finding smallest a[k] and making i=k; if current a[j] < some k which we have already passed through then j== that max;

then we compare the two differences.. and assign i and j

List findhighestdifindex(int a[])
{
int minindex=0,maxindex=0,max=0,min=23456;
List indexlist = new ArrayList();
for (int i = 0; i < a.length; i++) {
if(a[i]<min)
{
min=a[i];
minindex=i;
}
}
if(min<a.length)
{
for (int i = minindex+1; i < a.length; i++) {
if(a[i]>max)
{
max=a[i];
maxindex=i;
}
}
}
indexlist.add(maxindex);
indexlist.add(minindex);
return indexlist;
}

public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}

}

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

{public static void printMax(int []a){
int min,min1,max,x,x1,y;
min=max=min1=a[0];
x=x1=y=0;
for (int i=1;i<a.length;i++){
if(a[i]>=max){
max=a[i];
y=i;
}
else if(a[i]<min){
min1=a[i];
x1=i;
}
if((a[i]-min1)>(max-min)){
max=a[i];
min=min1;
x=x1;
y=i;
}
}
System.out.println( x);
System.out.println( y);
System.out.println( min);
System.out.println(max);
}


public static void main(String[] args) {
// TODO Auto-generated method stub
//int ar[]=new int[10];
int ar[]={5,15,3,10,20,1,19,0,8,16};
printMax(ar);
System.out.write(1);
}
}

Here is the running code enjoy

{public static void printMax(int []a){
		int min,min1,max,x,x1,y;
		min=max=min1=a[0];
		x=x1=y=0;
		for (int i=1;i<a.length;i++){
			if(a[i]>=max){
				max=a[i];
				y=i;
			}
			else if(a[i]<min){
				min1=a[i];
				x1=i;
			}
			if((a[i]-min1)>(max-min)){
				max=a[i];
				min=min1;
				x=x1;
				y=i;
			}
		}
		System.out.println( x);
		System.out.println( y);
		System.out.println( min);
		System.out.println(max);
		}
		
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int ar[]=new int[10];
		int ar[]={5,15,3,10,20,1,19,0,8,16};
		printMax(ar);
System.out.write(1);
	}

}

The below code is working. Let me know if you see any issues
{

public class MaxMin {

public static void main(String[] args) {
int [] arr = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21};
int y=0;
int i=0;
int j = 1;
while(arr[y]>arr[y+1])
y++;
int max = arr[y];
int min = arr[y+1];
int tmpi=y;
int tmpj=y+1;
int tmpMax =arr[y+1];
int tmpMin = arr[y];
boolean findMin=false,findMax=false;
for(int x = y+1; x <arr.length;x++){
if((arr[x] < min && arr[x] < tmpMin) || (findMax && tmpMax - arr[x] > max - min)){
tmpMin = arr[x];
tmpi=x;
findMin = true;
findMax = false;
}
if((arr[x] > max && arr[x] > tmpMax) || (findMin && arr[x] - tmpMin > max - min))
{
tmpMax = arr[x];
tmpj = x;
findMin = false;
findMax = true;

}
if(max - min < tmpMax - tmpMin && tmpj > tmpi){
max = tmpMax;
min = tmpMin;
i=tmpi;
j=tmpj;
}
}
System.out.println(i + " " + j);
}

}

}

int maxDiff( int* numbers, int size ) {
int max_diff = 0;
int min_ind = 0;
for( int i = 0 ; i < size; i++ ) {

if( numbers[i] < numbers[min_ind] ) {
min_ind = i;
}
else {
if ( ( numbers[i] - numbers[min_ind] ) > max_diff ) {
max_diff = numbers[i] - numbers[min_ind] ;
}
}
}

return max_diff;
}

#include <iostream>
using namespace std;

int finddiff(int *A, int len) {

int min = A[o];
int max = A[len-1];
int diff = 0;

int i = 0;
int j = len-1;

while( i <=j ) {
if(A[i] < min) { min = A[i]; }
if(A[j] > max) { max = A[j]; }
if( A[i] > A[j]) { j--; continue; }
if( diff < (max - min))
diff = max - min;

i++;
}

return diff;
}

int main() {

int A[] = { 2, 5, 10, -2, 27, 13, 24, -1};
int maxdiff = finddiff(A, 8);
cout << "Max diff = " << maxdiff << endl;

}




}


}

#include <iostream>
using namespace std;

int finddiff(int *A, int len) {

int min = A[o];
int max = A[len-1];
int diff = 0;

int i = 0;
int j = len-1;

while( i <=j ) {
if(A[i] < min) { min = A[i]; }
if(A[j] > max) { max = A[j]; }
if( A[i] > A[j]) { j--; continue; }
if( diff < (max - min))
diff = max - min;

i++;
}

return diff;
}

int main() {

int A[] = { 2, 5, 10, -2, 27, 13, 24, -1};
int maxdiff = finddiff(A, 8);
cout << "Max diff = " << maxdiff << endl;

}




}


}

Dynamic programming
{
int i,j,index,min,max;
min=max=i=j=0;
for (index=1; index<size; index++) {
if (a[index]>a[j]) {
j=index;
if (a[j]-a[i]>a[max]-a[min]) {
max=j;
min=i;
}
}
if (a[index]<a[i]) {
i=j=index;
}
}
}

1. minimumIn[1...i] = min(a[i], minimum[1...i-1]); O(n) time and space, left to right
2. maximumIn[n...i] = max(a[i], maximum[n...i+1]); O(n) time and space, right to left
3. find i, for which maximumIn[n...i] - minimumIn[1...i] is maximum, again O(n) time, no extra space

Take two variables
min and maxdiff,
Keep track of min element found so far and take difference of current element and the min value found so far. keep storing difference in the maxdiff variable.

at the end it will return the max differnce.
and for index keep there track too.

void arrayFindSubMax(int *a,int length,int *i,int *j)
{
	int max=0,sub,p,q;
	*i=0;
	*j=0;
	for(p=0,q=1;q<length;)
	{
		sub = a[q] - a[p];
		if(sub>max)
		{
			max = sub;
			*i = p;
			*j = q;
		}
		if(sub>0) q++;
		else {p=q;q++;}
	}
}

#include <stdio.h>

int main()
{

int array[5] = {10,4,2,-7,-1};
int i,j,count,min,max,result;

i=j=0;

min = array[0];
max = array[0];

for(count=1;count<5;count++)
{
if(min > array[count])
{
min = array[count];
i = count;
}

if(max < array[count])
{
max = array[count];
j=count;
}

}

printf("Min %d - %d\n",i,min);
printf("Max %d - %d\n",j,max);
result = max-min;
printf("Result of max and min -%d",result);
return 0;
}

public class Main
{
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        // TODO code application logic here
//        int values[] = {3, 5, 1, 2}; int expected[] = {0, 1};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};  int expected[] = {5, 6};
//        int values[] = {7, 5, 4, 3, 1, 6}; int expected[] = {4, 5};
//        int values[] = {5, 15, 2, 10, 20, 1, 17, 0, 8, 16}; int expected[] = {2, 4};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16}; int expected[] = {5, 6};
//        int values[] = {5, 15, 3, 10}; int expected[] = {0, 1};
//        int values[] = {2, 3, 1, 4, 5, 1, 6, 2, 3, 4}; int expected[] = {2, 6};
//        int values[] = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21}; int expected[] = {2, 9};
//        int values[] = { 2, 5, 10, -2, 27, 13, 24, -1}; int expected[] = {3, 4};
//        int values[] = {10, 4, 2, -7, -1}; int expected[] = {3, 4};
//        int values[] = {4, 10, 2, -7, -1}; int expected[] = {0, 1};
        indices(values, expected);
    }

    /**
     * one unsorted array is given.  Find out the index i and j, j > i for
     * which a[j] - a[i] is maximum.  perform in linear time complexity.
     *
     * @param values
     * @param expected
     * @return
     */
    public static final int[] indices(final int[] values, final int[] expected)
    {
//        int values[] = {3, 5, 1, 2}; int expected[] = {0, 1};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};  int expected[] = {5, 6};
//        int values[] = {7, 5, 4, 3, 1, 6}; int expected[] = {4, 5};
//        int values[] = {5, 15, 2, 10, 20, 1, 17, 0, 8, 16}; int expected[] = {2, 4};
//        int values[] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16}; int expected[] = {5, 6};
//        int values[] = {5, 15, 3, 10}; int expected[] = {0, 1};
//        int values[] = {2, 3, 1, 4, 5, 1, 6, 2, 3, 4}; int expected[] = {2, 6};
//        int values[] = {25, 15, 3, 10, 20, 3, 19, 5, 8, 21}; int expected[] = {2, 9};
//        int values[] = { 2, 5, 10, -2, 27, 13, 24, -1}; int expected[] = {3, 4};
//        int values[] = {10, 4, 2, -7, -1}; int expected[] = {3, 4};
//        int values[] = {4, 10, 2, -7, -1}; int expected[] = {0, 1};
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        int maxIndex = 0;
        int retMinIndex = 0;
        int retMaxIndex = 0;
        int maxDiff = 0;

        for(int i = 0; values.length > i; ++i)
        {
            if(min > values[i])
            {
                min = values[i];
                minIndex = i;

                // takes care of j > i constraint
                max = values[i];
                maxIndex = i;
            }
            else if(max < values[i])
            {
                max = values[i];
                maxIndex = i;
            }
            
            if(max - min > maxDiff)
            {
                maxDiff = max - min;
                retMinIndex = minIndex;
                retMaxIndex = maxIndex;
            }

            System.out.println("diff: " + (max - min));
        }

        int answer[] = new int[]{retMinIndex, retMaxIndex};

        System.out.println("answer: " + Arrays.toString(answer));
        System.out.println("expected: " + Arrays.toString(expected));

        return answer;
    }

int findMaxDiffPosition(int element[], int n, int& firstElementPos, int& lastElementPos)
{
int diff = element[1] - element[0];
int i,j;

i = 0;
j = 1;

while( i < n && j < n)
{
if (element[i] < element[j])
{
if ( (element[j] - element[i] ) > diff )
{
firstElementPos = i;
lastElementPos = j;
diff = element[j] - element[i];
}
j++;
}
else
{
i = j;
j = i + 1;
}
}
return diff;
}

#include<stdio.h>

void find_i_j(int a[], int n) {
	int i, j, k, minval, maxdiff;
	i=j=k=maxdiff=0;
	minval=a[0];

	for (k=1; k<n; k++) {
		 
		if (minval > a[k]) {
			minval=a[k];
			i=k;
			continue;
		}
		if ((a[k]-minval) > maxdiff) {
			maxdiff=a[k]-minval;
			j=k;
		}	
	}
	printf("i %d, val %d\nj %d, val %d\n", i+1, a[i], j+1, a[j]);
	
}

int main(void) {

	int a[10];
	int i;

	for (i=0;i<10;i++)
		scanf("%d",&a[i]);

	for (i=0;i<10;i++)
		printf("%d, ",a[i]);
	printf("\n");

	find_i_j(a, 10);
	return 0;
}

#include<stdio.h>

void find_i_j(int a[], int n) {
	int i, j, k, minval, maxdiff;
	i=j=k=maxdiff=0;
	minval=a[0];

	for (k=1; k<n; k++) {
		 
		if (minval > a[k]) {
			minval=a[k];
			i=k;
			continue;
		}
		if ((a[k]-minval) > maxdiff) {
			maxdiff=a[k]-minval;
			j=k;
		}	
	}
	printf("i %d, val %d\nj %d, val %d\n", i+1, a[i], j+1, a[j]);
	
}

int main(void) {

	int a[10];
	int i;

	for (i=0;i<10;i++)
		scanf("%d",&a[i]);

	for (i=0;i<10;i++)
		printf("%d, ",a[i]);
	printf("\n");

	find_i_j(a, 10);
	return 0;
}

have an array which is the same size as original
Initialize elements to ZERO


max_so_far = 0;

Start from the end (i = n-1; i >= 0; i--)
{
if (max_so_far > a[i])
{
max_so_far = a[i]
}
else
{
scan[i] = max_so_far-a[i];
}
}

max_so_far = scan[0];
int idx_min = 0;
for (i = 1 -> n-1)
{
if (max_so_far < scan[i])
{
max_so_far = scan[i]
idx_min = i;
}
}

// idx_min has the value which is an the min in subtraction

int to_find = scan[idx_min] + a[idx_min];
int idx_max = 0;
for(i = idx+1 -> n-1)
{
if (to_find == a[i])
{
idx_max = i;
break
}
}


// now idx_min has the min and idx_max has the max
a[idx_max] - a[idx_min] - should give the max diff

Pair<Integer, Integer> findMaxDiffIndices(int[] a) {
    Pair<Integer, Integer> p = new Pair<Integer, Integer>(0, 0);
    int i = 0;
    int j = 0;
    int cmin = 0;
    for (int k = 1; k < a.length; k++) {
      if (a[k] < a[i]) {
        cmin = k;
      } else if (a[k] - a[cmin] > a[j] - a[i]) {
        j = k;
        i = cmin;
      }
    }
    p.fst = i;
    p.snd = j;
    return p;
}

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
if( min == -1 && max == -1 )
min = i;
else
{
if( a[min] > a[i] )
if( max == -1 )
min = i;
if( contendermin == -1 || a[contendermin] > a[i] )
contendermin = i;
else if( max == -1 )
max = i;
else if( a[max] < a[i] )
{
max = i;
if( contendermin != -1 )
{
min = contendermin;
contendermin = -1;
}
}
}
}

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
	if( min == -1 && max == -1 )
		min = i;
	else
	{
		if( a[min] > a[i] )
			if( max == -1 )
				min = i;
			if( contendermin == -1 || a[contendermin] > a[i] )
				contendermin = i;
		else if( max == -1 )
			max = i;
		else if( a[max] < a[i] )
		{
			max = i;
			if( contendermin != -1 )
			{
				min = contendermin;
				contendermin = -1;
			}
		}
	}
}

int min, max, contendermin;
min = max = contendermin = -1;
for( int i=0; i<n; i++ )
{
	if( min == -1 && max == -1 )
		min = i;
	else
	{
		if( a[min] > a[i] )
			if( max == -1 )
				min = i;
			if( contendermin == -1 || a[contendermin] > a[i] )
				contendermin = i;
		else if( max == -1 )
			max = i;
		else if( a[max] < a[i] )
		{
			max = i;
			if( contendermin != -1 )
			{
				min = contendermin;
				contendermin = -1;
			}
		}
	}
}

Just a thought :- Can we use max-heap and min-heap to do it in linear time.

We can create min or max heap in linear time.

Comments Please.

#include <iostream>

using namespace std;
#define NUMBER 10
int main(){

int a[NUMBER] = {5, 15, 3, 10, 20, 1, 19, 0, 8, 16};

int minElement = a[0];
int maxDiff = a[1]-a[0];
int index1 = 0, index2 = 1, currDiff;

for(int i = 1; i<NUMBER; i++){
if(a[i] < minElement){
minElement = a[i];
currDiff = maxDiff;
}else{
currDiff = a[i] - minElement;
}
if(currDiff > maxDiff){
maxDiff = currDiff;
index2 = i;
}
}

minElement = a[index2] - maxDiff;

for(int i = 0; i<index2; i++){
if(a[i] == minElement){
index1 = i;
break;
}
}

cout<<"Maximum Diff is: "<<maxDiff<<endl;
cout<<"Index of min element and max element are : "<<index1<<" "<<index2<<endl;
system("pause");

return 0;
}

void main()
{
int a[]= {3, 5, 1, 2};
int MAX=0, i=0, j=0, m,t=0,b=0;
m= sizeof(a)/ sizeof(int);

for(j=1;j<m;j++)
{
if(a[j]>a[i])
{
if(a[j]-a[i]> MAX)
{
t=j;
b=i;
MAX= a[j]-a[i];
}
}
else
i=j;
}

printf("%d,%d,%d",MAX,b,t);
return;
}

void main()
{
int a[]= {15,13,11,7,4,0,-1};
int MAX=0, i=0, j=0, m,t=0,b=0;
m= sizeof(a)/ sizeof(int);

for(j=1;j<m;j++)
{
if(a[j]>a[i])
{
if(a[j]-a[i]> MAX)
{
t=j;
b=i;
MAX= a[j]-a[i];
}
}

else if(a[j]==a[i])
continue;

else
i=j;
}

if(MAX==0)
{
i=1;
MAX=a[1]-a[0];
b=0;
t=1;
for(j=2;j<m;j++)
{
if(a[j]-a[i]> MAX)
{
MAX= a[j]-a[i];
b=i;
t=j;
}
else
i=j;
}
}

printf("%d,%d,%d",MAX,b,t);
return;

}

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  int size,curr,curr_id,min_id,max_id,diff;  
  printf("Enter the size of array : ");
  scanf("%d",&size);
  int *arr=(int*)malloc(sizeof(int)*size);
  int i=0;
  for(i=0;i<size;i++)
  {
          scanf("%d",&arr[i]);
  }
  max_id=1;
  min_id=0;
  diff=arr[1]-arr[0];
  curr=arr[1];
  curr_id=1;
  if(arr[1]>arr[0])
  {
                   curr=arr[0];
                   curr_id=0;
  }
  for(i=2;i<size;i++)
  {
                  if(arr[i]-curr >= diff)
                  {
                           diff=arr[i]-curr;
                           min_id=curr_id;
                           max_id=i;     
                  }
                  if(arr[i]<curr)
                  {
                            curr=arr[i];
                            curr_id=i;
                  } 
  }
  printf("Max diff is %d\n",diff);
  printf("Min index value is %d\n",min_id);
  printf("Max index value is %d\n",max_id);
  system("PAUSE");	
  return 0;
}

I think taking additional space this problem can be solved in O(n).
1) Pass through the array and create another array which holds the value of the differences of two adjacent elements.
b[i]=a[i+1]-a[i]
2) Find the maximum sub array sum for array b, which can be found in O(n) time. For any sub array sum as the answer b[l] to b[r] the value will actually be a[l+1]-a[l]+a[l+2]-a[l+1]...a[r+1]-a[r]. which reduces to a[r+1]-a[l] where r+1>l and this the maximum such value.

import sys

A = [int(n) for n in sys.stdin.read().strip().split()]
i, j = 0, 1
mini = 0
minup2n = A[mini]
n = 2
while n < len(A):
  if A[n - 1] < minup2n:
    mini = n - 1
    minup2n = A[mini]
  if A[n] - minup2n > A[j] - A[i]:
    i = mini
    j = n
  n = n + 1

print 'A[%d] = %d, A[%d] = %d' % (i, A[i], j, A[j])

int minCandidate = 0;
i = 0;
j = 0;
for (int k = 1; k < a.Length; k++)
{
    if (a[k] > a[j])
    {
        j = k;
    }
    else if (a[k] < a[minCandidate])
    {
        minCandidate = k;
    }

    if (j > minCandidate && a[j] - a[minCandidate] > a[j] - a[i])
    {
        i = minCandidate;
    }
    if (a[j] - a[i] < a[k] - a[minCandidate])
    {
        i = minCandidate;
        j = k;
    }
}

private static void MaxDifference(int[] a) {
		if(a.length == 0){
			System.out.println("Empty Array");
		}
			
		int i = 0, minIndex = 0;
		int j = a.length - 1, maxIndex = a.length - 1;
		int maxDiff = a[j] - a[i];
		int count = 0;
		while(count < a.length - 1){
			if(a[maxIndex] - a[i+1] > maxDiff && a[i+1] < a[minIndex] && maxIndex > i+1){
				minIndex = i+1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			if(a[j - 1] - a[minIndex] > maxDiff && a[j-1] > a[maxIndex] && minIndex < j-1){
				maxIndex = j-1;
				maxDiff = a[maxIndex] - a[minIndex];
			}
			i++;j--;count++;
			System.out.println("count :" + (count) + " difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		}
		System.out.println("difference : " + maxDiff + "  min value " + a[minIndex] + " max value " + a[maxIndex]);
		
	}

Correct me if I am wrong

Algo:
i = 0, j = size-1

while(i<j)
{
while (a[i]> a[i+1]) i++
while (a[j]<a[j-]) j--;
if a[j]-a[i] > maxdiff
overwrite maxdiff
}

Correct me if I am wrong

Algo:
i = 0, j = size-1

while(i<j)
{
while (a[i]> a[i+1]) i++
while (a[j]<a[j-]) j--;
if a[j]-a[i] > maxdiff
overwrite maxdiff
}

Here the no at index j has to be the maximum element of the array and no at index i has to be the minimum. So we can have 4 variables max, min, maxIndex and minIndex. Initially max=min=A[0] and maxIndex=minIndex=0. In linear time, traverse the array and find the minimum and maximum nos and return their corresponding indices.

public static void FindMaxDiffIndices(int[] array)
{
    int min = Int32.MaxValue;
    int max = Int32.MinValue;
    int max_i = 0, min_i = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
            min_i = i;
        }
        if (array[i] > max)
        {
            max = array[i];
            max_i = i;
        }
    }
    if (max_i > min_i)
        Console.WriteLine("{0}, {1}", min_i, max_i);
    else
    {
        int min1 = Int32.MaxValue;
        int min1_i = 0;
        for (int i = 0; i < max_i; i++)
        {
            if (array[i] < min1)
            {
                min1 = array[i];
                min1_i = i;
            }
        }
        int max1 = Int32.MinValue;
        int max1_i = min_i;
        for (int i = min_i; i < array.Length; i++)
        {
            if (array[i] > max1)
            {
                max1 = array[i];
                max1_i = i;
            }
        }
        if (max - min1 > max1 - min)
        {
            Console.WriteLine("{0}, {1}", min1_i, max_i);
        }
        else
        {
            Console.WriteLine("{0}, {1}", min_i, max1_i);
        }
    }
}

public static void FindMaxDiffIndices(int[] array)
{
    int min = Int32.MaxValue;
    int max = Int32.MinValue;
    int max_i = 0, min_i = 0;
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] < min)
        {
            min = array[i];
            min_i = i;
        }
        if (array[i] > max)
        {
            max = array[i];
            max_i = i;
        }
    }
    if (max_i > min_i)
        Console.WriteLine("{0}, {1}", min_i, max_i);
    else
    {
        int min1 = Int32.MaxValue;
        int min1_i = 0;
        for (int i = 0; i < max_i; i++)
        {
            if (array[i] < min1)
            {
                min1 = array[i];
                min1_i = i;
            }
        }
        int max1 = Int32.MinValue;
        int max1_i = min_i;
        for (int i = min_i; i < array.Length; i++)
        {
            if (array[i] > max1)
            {
                max1 = array[i];
                max1_i = i;
            }
        }
        if (max - min1 > max1 - min)
        {
            Console.WriteLine("{0}, {1}", min1_i, max_i);
        }
        else
        {
            Console.WriteLine("{0}, {1}", min_i, max1_i);
        }
    }
}

/*
One unsorted array is given.Find out the index i and j ,j> i for which 
a[j] - a[i] is maximum.perform in linear time complexity.
*/

#include<iostream>
using namespace std;

int main()
{
    int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
//    int arr[] = {7, 5, 2};
    int size = sizeof(arr)/sizeof(*arr);
    
    int tillMin = arr[0];
    int tillMax = arr[1];    
    int diff = tillMax-tillMin;
    int valI=0, valJ = 1;    
    for(int i=2;i<size;i++)
    {
        if(diff < arr[i]-tillMin)
            diff = arr[i]-tillMin;
        
        if(arr[i] > tillMax)
        {
            valJ = i;
            tillMax = arr[i];
        }
        else if(arr[i] < tillMin)
        {
            valI = i;
            tillMin = arr[i];
        }
    }
    
    cout<<"  Maximum difference is :- "<<diff<<"  i = "<<valI<<"  j = "<<valJ<<endl;
    system("PAUSE");
    return 0;
}

/*
One unsorted array is given.Find out the index i and j ,j> i for which 
a[j] - a[i] is maximum.perform in linear time complexity.
*/

#include<iostream>
using namespace std;

int main()
{
    int arr[] = {1, 12, 3, 6, 2, 8, 17, 9, 1};
//    int arr[] = {7, 5, 2};
    int size = sizeof(arr)/sizeof(*arr);
    
    int tillMin = arr[0];
    int tillMax = arr[1];    
    int diff = tillMax-tillMin;
    int valI=0, valJ = 1;    
    for(int i=2;i<size;i++)
    {
        if(diff < arr[i]-tillMin)
            diff = arr[i]-tillMin;
        
        if(arr[i] > tillMax)
        {
            valJ = i;
            tillMax = arr[i];
        }
        else if(arr[i] < tillMin)
        {
            valI = i;
            tillMin = arr[i];
        }
    }
    
    cout<<"  Maximum difference is :- "<<diff<<"  i = "<<valI<<"  j = "<<valJ<<endl;
    system("PAUSE");
    return 0;
}

Python3
if a[j] - a[i] isn't abs:

_input = [9, 3, 4, 0, 5, 7, 4, 2, 1, 6]
i_index = _input.index(min(_input))
j_index = _input.index(max(_input[i_index:]))
print (i_index, j_index)

From looking at other people's comments, I get the sense that a[j] - a[i] is abs.

int i=0;
int j=n-1;

while(i!=j)
{
	if (A[i] < A[j])
	{
		cout<<j<<i;
		break;
	}	
	else if (A[i] < A[j-1])
	{	
		cout<<j-1<<i;
		break;
	}
	else if (A[i+1] < A[j])
	{
		cout<<j<<i+1;
		break;
	}
	else
	{
		i++;
		j--;
	}
}

is there any trick?i feel this simple enough. Pls correct if wrong

for(i=0;j=A.length-1;j>=0;i++,j--)
  if(A[i]<A[j]){
    print(j-i)
    break
  }