Skip to content

Instantly share code, notes, and snippets.

@FermiDirak
Created September 15, 2019 04:23
Show Gist options
  • Save FermiDirak/8d2bd791d57393309fce07bda838effb to your computer and use it in GitHub Desktop.
Save FermiDirak/8d2bd791d57393309fce07bda838effb to your computer and use it in GitHub Desktop.
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var kConcatenationMaxSum = function(arr, k) {
const anyNegative = arr.some(a => a < 0);
if (!anyNegative) {
return (arr.reduce((a, b) => a + b, 0) * k) % 1000000007;
}
const allNegative = arr.every(a => a <= 0);
if (allNegative) { return 0; }
const maxSingle = maxSubArray(arr) % 1000000007;
if (k === 1) {
return maxSingle;
}
const doubleArr = [...arr, ...arr];
const maxDouble = maxSubArray(doubleArr) % 1000000007;
if (k === 2) {
return maxDouble;
}
const tripleArr = [...arr, ...arr, ...arr];
const maxTriple = maxSubArray(tripleArr) % 1000000007;
if (k === 3) {
return maxTriple;
}
if (maxDouble === maxTriple) {
return maxDouble;
}
return (maxSingle + ((maxTriple - maxDouble) * (k - 1))) % 1000000007;
};
const maxSubArray = (nums) => {
let maxTotal = nums[0];
let sum = 0;
for(let i of nums) {
sum += i;
if(maxTotal < sum) {
maxTotal = sum;
}
if(sum < 0) {
sum = 0;
}
}
return maxTotal;
};
@sssss465
Copy link

reason for this code??

 if (maxDouble === maxTriple) {
        return maxDouble;
    }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment