Skip to content

Instantly share code, notes, and snippets.

@germanescobar
Created September 18, 2021 00:43
Show Gist options
  • Save germanescobar/27e805d3e2d0e38b3ed3f106f722d642 to your computer and use it in GitHub Desktop.
Save germanescobar/27e805d3e2d0e38b3ed3f106f722d642 to your computer and use it in GitHub Desktop.
var kConcatenationMaxSum = function(arr, k) {
let maxSum = calculateMaxSubArraySum(arr)
if (k === 1) return maxSum
let newArr = [...arr, ...arr]
let sum = calculateMaxSubArraySum(newArr)
if (sum <= maxSum) {
return maxSum
}
maxSum = sum
newArr = [...newArr, ...arr]
sum = calculateMaxSubArraySum(newArr)
if (sum <= maxSum) {
return maxSum
}
return maxSum + (sum - maxSum) * (k - 1)
};
function calculateMaxSubArraySum(newArr) {
let maxSum = 0
for (let i=0; i < newArr.length; i++) {
for (let j=i; j < newArr.length; j++) {
let sum = 0
for (let k=i; k <= j; k++) sum += newArr[k]
if (sum > maxSum) {
maxSum = sum
}
}
}
return maxSum;
}
@germanescobar
Copy link
Author

Esta solución todavía no funciona. Ayuda!

@raulsant20
Copy link

Buenas noches, dejó mi aporte al problema

var kConcatenationMaxSum = function(arr, k) {
  let MOD=1000000007
  let n=arr.length

  const sumMax = (q,n)=>{
    let rep=0
    let sum=0
    let max=0
    while(rep<q){
      for(let i=0;i<n;i++){
        sum+=arr[i]
        sum=Math.max(0,sum)
        max=Math.max(max,sum)
      }
      rep++
    }
    return max
  }

  if(k===1) return sumMax(k,n)%MOD
  else {
    let max=sumMax(2,n)
    let sumMed=arr.reduce((acc,x)=>acc+x,0)*(k-2)
    return Math.max(max,sumMed+max)%MOD
  }
};

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