Open lpatmo opened 5 years ago
//BRUTE FORCE O(N^2)
function maxSumBruteForce(arr) {
let max = -Infinity;
let sum = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = i; j < arr.length; j++) {
//0 to 0, 0 to 1, 0 to 2... etc.
//1 to 1, 1 to 2, 1 to 3, etc. up to .length
//2 to 2, etc.
//if (i <= j) { //only need this if j started at 0
sum += arr[j];
console.log(sum+" i: " + i + " j: "+j)
// }
max = Math.max(sum, max)
}
sum = 0;
}
return max;
}
console.log("Answer "+maxSumBruteForce(arr))
//Alternative:
//find midpoint
//find max on left side
//find max on right side
//find max around the midpoint
/*Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far*/
//Kadene's solution
function maxSumKadene(arr) {
let maxCurrent = 0;
let maxFinal = 0;
for (let i = 0; i < arr.length; i++) {
maxCurrent = maxCurrent + arr[i];
if (maxCurrent < 0) {
maxCurrent = 0;
}
if (maxFinal < maxCurrent) {
maxFinal = maxCurrent;
}
}
return maxFinal;
}
console.log("Answer "+maxSumKadene(arr))
Problem: https://leetcode.com/problems/maximum-subarray/