Find the maximum difference in an unsorted array with the index of max greater than min. array cant be sorted

Question

Sigiloso · Accepted Answer

This should do in single pass O(N), with min value being always before the max:

int max_dist(const vector& data, size_t& start, size_t& end)
{
    size_t min = 0;
    size_t max = 0;
    start = end = 0;
    if (data.size() == 0)
    {
        return 0;
    }
    for (size_t i = 1; i  data[max])
        {
            max = i;
            if (data[max] - data[min] > data[end] - data[start])
            {
                // found new biggest distance
                start = min;
                end = max;
            }
        }
    }
    return data[end] - data[start];
}

candidate · Answer

you can do it by traversing the array from the end in a single pass
int diff = 0;
int curMax = a[a.length-1];
for(int i = a.length - 2; i >= 0; --i) {
  if(curMax > a[i])
    diff = max(diff, curMax - a[i])
  curMax = max(curMax, a[i])
}
// curMax will have max diff

Sigiloso · Answer

It could have been solved by traversing the array, maintaining min , its index and max and its index (maxindex > minindex) and returning difference.
I suggested a dynamic programming approach of storing the difference seen till now in a matrix..but I am not sure if it was correct.

Theja · Answer

This solution finds max element, min element in given array with time complexity of O(n). But I still didn't figure out how to use fact that index of max is greater than index of min

public class FindMaxMin{
    public static void main(String[] args){
        int[] a = {1,3,5,22,15,34,2,674,56};
        int min = findMin(a);//O(n)
        int max = findMax(a);//O(n)
        System.out.println("Max is "+max);
        System.out.println("Min is "+min);
        System.out.println("Maximum difference is "+max - min);
    }
    public static int findMax(int[] input){
        for(int i = 0; i  input[i+1]){
                int temp = input[i];
                input[i] = input[i+1];
                input[i+1] = temp;
            }
        }
        return input[input.length-1];
    }
    public static int findMin(int[] input){
        for(int i = 0; i < input.length-1; i++){
            if(input[i] < input[i+1]){
                int temp = input[i];
                input[i] = input[i+1];
                input[i+1] = temp;
            }
        }
       return input[input.length-1];
    }
}

Himanshu Verma · Answer

#include
#include
int main()
{
        int array[]={0,4,6,89,1,5,333,35,67,9,888};
        int min=0;
        int max=1;
        int dist=array[1]-array[0];
        int i;
        for(i=2; iarray[max])
                {
                        max=i;
                        if(dist  min)
                                dist=array[max]-array[min];
                      //  printf(" dist is %d
", dist);
                        continue;
                }
                if(array[i] < array[min])
                {
                        min=i;
                }
        }
        printf("dist= %d
", dist);
}

anonymously · Answer

for(i = length; i >= 0; i--){
    for(j = i-1; j >= 0; j--){
        if((a[i] - a[j]) > diff ){
            diff = a[i] - a[j];
            max = i; min = j; 
        }
    }
}
if(diff > 0){
printf("diff: %d, max: a[%d]=%d min: a[%d]=%d", diff, max, a[max], min, a[min]);
}

Anonymous · Answer

Don't you think it is maximum sum  sub-array problem? E.g.: One person already mentioned: 
Buy and Sell stocks. You can't sell before you buy. The buying cost must be smaller than selling price.

Bloomberg

Pergunta de entrevista da empresa Bloomberg

Respostas da entrevista

Empresas seguidas

Buscas de vagas