CareerCup

int Array::MaxDiff(vector<int> arr){
if(arr.size()==0) return 0;
int n=arr.size(),i,j;

vector<int> Lmin(n,0);
vector<int> Rmax(n,0);

Lmin[0]=arr[0];
for(i=1;i<n;i++)
Lmin[i]=min(arr[i],Lmin[i-1]);

Rmax[n-1]=arr[n-1];
for(i=n-2;i>=0;i--)
Rmax[i]=max(arr[i],Rmax[i+1]);

int maxdiff=0;
i=0,j=0;

while(i<n&&j<n){
if(Lmin[i]<Rmax[j]){
maxdiff=max(maxdiff,j-i);
j++;
}
else i++;
}

return maxdiff;
}

O(n) time and O(n) space solution. Tested! The key observation is the two auxiliary arrays LMin and RMax which saves the smallest value left of i and biggest value right of i

<pre lang="" line="1" title="CodeMonkey31266" class="run-this">I agree it's a little dumb, but it's the first idea which came to my mind, and it works.
Idea - recurse the step (j-i) downwards, starting with n-1;

static bool GetIAndJ(int[] a, ref int i, ref int step)
{
if (step == 0)
{
return false;
}
if (step >= a.Length)
{
throw new ArgumentException();
}
for (i = 0; i + step < a.Length; i++)
{
if (a[i] < a[i + step])
{
return true;
}
}
//else recur
step--;
i = 0;
return GetIAndJ(a, ref i, ref step);
}

//**** USAGE:
static void Main(string[] args)
{
int[] a = { /*whatever int values you desire*/ };

int i=0, step=a.Length-1;

if (GetIAndJ(a, ref i, ref step))
{
Console.WriteLine(i + " " + step);
}
}</pre><pre title="CodeMonkey31266" input="yes">Test cases ?</pre>

<pre lang="" line="1" title="CodeMonkey25519" class="run-this">

void maxji (int a[], int N, int *resi, int *resj) {
int i, j;
int previ, maxdist, maxi;

j = N-1;
while((a[j] < a[0]) && (j != 0)) --j;
previ = 0; maxi = 0; maxdist = j;


for (i = 1; i <= (N-maxdist-1); ++i) {
if (a[i] >= a[previ]) continue;
previ = i; j = N-1;
while((a[j] < a[i]) && (j != i)) --j;

if ((j - i) > maxdist) {
maxi = i; maxdist = j - i;
}

}
*resi = maxi; *resj = maxi + maxdist;
}

main () {

int a[]={3,1,4,5,2,1,2};
int maxi, maxj;

maxji(a, 7, &maxi, &maxj);
printf("\nN: %d i: %d j: %d dist: %d\n", sizeof(a), maxi, maxj, (maxj-maxi));
}
</pre><pre title="CodeMonkey25519" input="yes">
</pre>

Wrong answer. It wants two elements that maximizes j-i while a[i] < a[j]. your maximzies a[j]-a[i].

My solution takes O(n\log n). First we sort.
Now, for every index j, you need to find among all elements with a[i] < a[j] what is the minimum index.
With this, you can make a min-heap of all indices of all elements with a[i] < a[j].

I hope it is clear

@geliang: wow nice soln...had to spend lotta time to just understand and debug geliang's soln :)
but do we require LMIN matrix? i mean what if we just keep
arr[i] < RMAX[j] in stead of LMIN[i] < RMAX[j] not being able to figure out why LMIN is required if we are only interested in j-i > 0

@geliang wow nice soln had to spend time just to understand what it's trying to do..
but still not being able to why LMIN is reqd? what if we just keep
arr[i] < RMAX[i] if we are just interested in j-i > 0

public static int maxdiff(int [] array){
for(int i=array.length-1; i>0; i--){
int start=0;
int end = 0+i;
while(end<array.length){
if(array[start]<array[end]){
return i;
}
else{
start++;
end++;
}
}
}
return 0;
}

idea:
1) scan the array.
2) use three auxiliary numbers to keep the current max and the current min, and the current max_diff = max-min.
3) if max is updated, update max_diff;
4) if min is updated, do not update max_diff;

One pass; O(n) time, O(1) space

{{
int findMaxDiff(int array[]){
// check
if(array==null || array.length < 2) return -1;

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

for(int i=1; i<array.length; i++){
// update min if current value < min
if(array[i] < min) min = array[i];

// update both max and max_diff if current value > max
if(array[i] > max){
max = array[i];
max_diff = max-min;
}
}

return max_diff;
}
}}

0(nlgn + n) average case:

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void sort(int *a, int n, int *b)
{
	if (n < 2) return;

	int pivot = a[n-1];
	int pivotb = b[n-1];

	int small = 0;
	int large = n - 2;

	while (small < large)
	{
		if (a[small] <= pivot)
		{
			++small;
		}
		else if (a[large] >= pivot)
		{
			--large;
		}
		else
		{
			swap(&a[large], &a[small]);
			swap(&b[large], &b[small]);
		}
	}

	a[n-1] = a[large];
	b[n-1] = b[large];
	a[large] = pivot;
	b[large] = pivotb;

	sort(a, small, b);
	sort(a + small + 1, n - small - 1, b + small + 1);
}

int maxIDiff(int *a, int n)
{
	int *b = new int[n];
	
	for (int i = 0; i < n; ++n)
	{
		b[i] = i;
	}

	sort(a, n, b);

	int maxDiff = -1;
	int minSeenSoFar = b[0];

	for (int i = 0; i < n; ++i)
	{
		if (b[i] < minSeenSoFar)
		{
			minSeenSoFar = b[i];
		}
		else if (maxDiff < (b[i] - minSeenSoFar))
		{
			maxDiff = (b[i] - minSeenSoFar));
		}
	}

	return maxDiff;
}

One solution can be like that.
Initialize max = -1,imax =-1,jmax = -1
First compare the first element with all elements find the largest j for which a{j] > a[0]. max = j,,imax = i,jmax = j;
Now in second step compare the last element with all previous elements find the largest j for which a{length-1] > a[i]. max = lengh -1 -j,imax = i,jmax = j;
We need to repeat above steps until max != -1 i.e we have found max and that is going to be our result.

Below is the Java code to solve the problem :

public class FindMaxIndexDiff {

	private int findDiff(int[] arr) {
		int i = 0, j = 0, maxVal = 0, prevMinIndex = 0, k = 0;
		while (i < arr.length - 1) {
			j = arr.length - 1;
			// Find closest element from end greater than arr[i]
			while (j > i && arr[j] < arr[i]) {
				j--;
			}
			if(j == arr.length - 1){
				k = j;
			}else{
				k = j+1;
			}
			// Update maxVal if index diff is greater than current value
			if(arr[k] > arr[prevMinIndex]){
				if(k - prevMinIndex > maxVal){
					maxVal = k - prevMinIndex;
				}
			}
			// Find next element less than current min (i.e. arr[prevMin])
			i++;
			while(i < arr.length - 1 && arr[i] > arr[prevMinIndex]){
				i++;
			}
			prevMinIndex = i;
		}
		return maxVal;
	}

	public static void main(String[] args) {
		FindMaxIndexDiff findMaxIndexDiff = new FindMaxIndexDiff();
		int[] arr = { 1, 4, 6, 5, 9, 14, 19, 8 };
		System.out.println("Max Diff = " + findMaxIndexDiff.findDiff(arr));
		int[] arr_2 = { 1, 4, 6, 5, 9, 8 };
		System.out.println("Max Diff = " + findMaxIndexDiff.findDiff(arr_2));
		int[] arr_3 = { 4, 3, 2, 1, 0 };
		System.out.println("Max Diff = " + findMaxIndexDiff.findDiff(arr_3));
		int[] arr_4 = { 3, 1, -4, 5, 2, 0, 2, 9, 10, 11 };
		System.out.println("Max Diff = " + findMaxIndexDiff.findDiff(arr_4));
	}
}

Output
-----------
Max Diff = 7
Max Diff = 5
Max Diff = 0
Max Diff = 9

private static int[] findIJ(int[] a) {

		int diff = a.length - 1;
		while (diff >= 0) {
			int j = a.length - 1;
			int i = j - diff;

			while (i >= 0) {
				if (a[i] < a[j]) {
					int[] ks = new int[] { i, j };
					return ks;
				} else {
					i--;
					j--;
				}
			}

			diff--;
		}

		return null;

	}

Use 2 pointers on the array, start by checking i=0, j=a.length-1 (diff = a.length-1)
If a[i] >= a[j] decrement diff and check
i=1, j = a.length-1
i=0, j = a.length-2

etc until you find what you need...

public static int[] findIJ(int[] a) {
		int diff = a.length - 1;
		while (diff >= 0) {
			int j = a.length - 1;
			int i = j - diff;

			while (i >= 0) {
				if (a[i] < a[j]) {
					int[] ks = new int[] { i, j };
					return ks;
				} else {
					i--;
					j--;
				}
			}

			diff--;
		}

		return null;

	}

l=strlen(A);
max=0;
for(i=0; i<l; i++)
  for(j=i+1; j<l; j++)
    if(A[i]<A[j])
      if((j-i)>max)
        {
        max=j-i;
        sovj=j;
        sovi=i;
        }

1 #include <iostream>
  2
  3
  4 #define INT_MAX 11
  5 using namespace std;
  6
  7 int largetSubSequence(int arr[], int len) {
  8     int *intmap = new int[INT_MAX];
  9
 10     for(int i = 0; i < len; i++) {
 11         intmap[arr[i]] = 1;
 12     }
 13
 14     int last = -1;
 15     int count = 0;
 16     int maxCount = 0;
 17     for(int i = 0; i < INT_MAX; i++) {
 18         if(last == -1) {
 19             last = intmap[i];
 20             count++;
 21         } else {
 22             if(intmap[i]==1) {
 23                 count++;
 24             } else {
 25                 count = 0;
 26             }
 27             last = intmap[i];
 28         }
 29         if(count > maxCount)
 30             maxCount = count;
 31     }
 32
 33     delete intmap;
 34     return maxCount;
 35 }
 36
 37 int main() {
 38     int arr[] = {1,6,10,4,7,9,5};
 40
 41     cout << largetSubSequence(arr, sizeof(arr)/sizeof(int)) << endl;
 42
 43     return 0;
 44 }

1 #include <iostream>
  2 #include <vector>
  3
  4 #define INT_MAX 11
  5 using namespace std;
  6
  7 int largetSubSequence(int arr[], int len, vector<int>& vec) {
  8     int *intmap = new int[INT_MAX];
  9
 10     for(int i = 0; i < len; i++) {
 11         intmap[arr[i]] = 1;
 12     }
 13
 14     int last = -1;
 15     int count = 0;
 16     int maxCount = 0;
 17     for(int i = 0; i < INT_MAX; i++) {
 18         if(last == -1) {
 19             last = intmap[i];
 20             count++;
 21         } else {
 22             if(intmap[i]==1) {
 23                 count++;
 24             } else {
 25                 count = 0;
 26             }
 27             last = intmap[i];
 28         }
 29         if(count > maxCount)
 30             maxCount = count;
 31     }
 32
 33     delete intmap;
 34     return maxCount;
 35 }
 36
 37 int main() {
 38     int arr[] = {1,6,10,4,7,9,5};
 39     vector<int> vec;
 40
 41     cout << largetSubSequence(arr, sizeof(arr)/sizeof(int), vec) << endl;
 42
 43     return 0;
 44 }

public class Solution{

  public int find_maximum( int[] arr ){
  
    int len = arr.length,p=0, q = 1,res = 0;
    if(len <= 1) return 0;
    int[] minList = int[len] , maxList = int[len];
    minList[0] = arr[0];
    maxList[len-1] = arr[len-1];
    for(int i = 1; i < len ; i++) 
      minList[i] = Math.min(arr[i] , minList[i-1]); 
    for(int i = len -2 ; i> 0 ; i--) 
      maxList[i] = Math.max(arr[i] , maxList[i+1]); 
    while(p < len && q< len){
      if(maxList[q] > minLIst[p] ) 
        q++; 
      else 
        p++; 
      
      res = math.max(q-p , res);
    }
    return res;
  }
}

#include<stdio.h>
#include<string.h>
#define LEN 7
int a[LEN] = {18,10,8,6,1,2,4};
int maxx[LEN];
int max(int i, int j) {

	return a[i] > a[maxx[j]] ? i:maxx[j];
}
int main() {

	int i, j, maxdiff = -1;
	maxx[LEN-1] = LEN - 1 ;
	for(i = LEN-2; i >= 0; i--) {
		maxx[i] = max(i, i+1);

	}
	for(i = 0; i < LEN; i++)
		printf("%d ", maxx[i]);
	i = 0; j = 0;
	while(j < LEN) {
		if(a[i] > a[maxx[j]]) {
			i = a[i] > a[i+1] ? i+1:i;

		}
		else {
			maxdiff = maxdiff > maxx[j] - i ? maxdiff: maxx[j] - i;

			j = maxx[j] + 1;
		}

	}	
	 maxdiff = maxdiff > maxx[j] - i ? maxdiff: maxx[j] - i;

	printf("%d\n", maxdiff);
}

}

If we simply find the max and min in the array and store the indexes will it not solve the problem ?


void fun(int a[SIZE])
{
int min, max , index_min, index_max;
int i ;

min = 10000;
max = -10000;

for(i=0; i<SIZE; i++)
{
if(a[i]<min)
{
index_min = i;
min = a[i];
}
if(a[i]>max)
{
index_max = i;
max = a[i] ;
}

}

printf("%d,%d",index_max, index_min);

}

I think the solution is much simpler:
{
public static void maxDiff(int[] array)
{
if (array.length == 0)
return;

for (int i=0, j=array.length; i<j; i++, j++)
{
if (array[i] < array[j])
{
System.out.println(i + "," + j);
}
}
return;
}
}