Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find maximum difference in array

Tags:

javascript

I'm working on an algorithm to return the difference of any pair of numbers, such that the larger integer in the pair occurs at a higher index (in the array) than the smaller integer.

Examples...

Array: [2, 3, 10, 2, 4, 8, 1]

Solution: 10 - 2 = 8

Output: 8


Array: [7, 9, 5, 6, 3, 2]

Solution: 9 - 7 = 2

Output: 2


Here is what I have but it doesn't work for all tests...

var a = [22, 2, 4, 5, 6, 444, 1, 666];

// declare variables
var minNumber = a[0],                   // initilize to first element
    maxNumber = a[0],                   // --- ^
    minNumberIndex = 0,                 // min index
    maxNumberIndex = a.length - 1;      // max index

// loop through each element in array
for(i = 0; i < a.length; i++) {

    // find min
    if (a[i] < minNumber && i < maxNumberIndex) {
        minNumber = a[i];
        minNumberIndex = i;
    }

    // find max
    if (a[i] >= maxNumber && i > minNumberIndex) {
        maxNumber = a[i];
        maxNumberIndex = i;
    }
}

// return results
console.log("max: \t" + maxNumber);
console.log("min: \t" + minNumber + "index: " + minNumberIndex);
console.log(maxNumber - minNumber);  

Please help!

like image 585
Kyle Avatar asked Apr 12 '15 03:04

Kyle


2 Answers

O(n) solution:

function maxDifference(arr) {
  let maxDiff = -1;
  let min = arr[0];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > min && maxDiff < arr[i] - min) {
      maxDiff = arr[i] - min;
    }

    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return maxDiff;
}

console.log(maxDifference([1, 2, 3])); //2
console.log(maxDifference(3, 2, 1)); //-1
console.log(maxDifference([2, 3, 10, 2, 4, 8, 1])); //8
console.log(maxDifference([7, 9, 5, 6, 3, 2])); //2
console.log(maxDifference([22, 2, 4, 5, 6, 444, 1, 666])); //665
console.log(maxDifference([7, 9, 5, 6, 3, 2])); //2
console.log(maxDifference([666, 555, 444, 33, 22, 23])); //1
console.log(maxDifference([2, 3, 10, 2, 4, 8, 1])); //8
like image 187
Volodymyr Myshko Avatar answered Sep 30 '22 15:09

Volodymyr Myshko


let MaxDifference = arr => {
  let maxDiff = null;
  for(let x = 0; x < arr.length; x++){
    for(let y = x+1; y < arr.length; y++){
        if(arr[x] < arr[y] && maxDiff < (arr[y] - arr[x])){
            maxDiff = arr[y] - arr[x]
        }
    }
  }
  return maxDiff === null ? -1 : maxDiff;
}
like image 34
DevDeb Avatar answered Sep 30 '22 14:09

DevDeb