Skip to content

Instantly share code, notes, and snippets.

@rodcisal
Created April 12, 2021 13:13
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rodcisal/949f4045d5ca765dfda2f0fb706dd3c2 to your computer and use it in GitHub Desktop.
// const testArr = [1,6,1,6,9];
const t1 = [1,5,0,6,7,10,10,12,7,7,7,8,7];
const t2 = [1,2,3,4];
function closestMaxInArray(arr) {
let maxIdx = 0;
let minIdx = 0;
for (let idx in arr) {
const val = arr[idx];
if (val >= arr[maxIdx]) {
maxIdx = +idx;
}
}
for (let idx in arr) {
const val = arr[idx];
if (val <= arr[minIdx] && idx < maxIdx) {
minIdx = +idx;
}
}
return {minIdx, maxIdx};
}
function maxProfit (arr) {
const cl = closestMaxInArray(arr);
let profit = arr[cl.maxIdx] - arr[cl.minIdx];
let rest = [arr.slice(0, cl.minIdx), arr.slice(cl.maxIdx + 1, arr.length)]
rest.forEach(ra => {
if (ra.length > 2) {
const r = maxProfit(ra);
profit = profit + r;
}
if (ra.length === 2 && ra[1] > ra[0]) {
profit = profit + (ra[1] - ra[0]);
}
})
return profit;
}
const s0 = maxProfit([3,2,1])
const s = maxProfit(t1);
const s2 = maxProfit(t2);
const s3 = maxProfit([1,6,1,6,9]);
const s4 = maxProfit([2,1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment