Maximum subarray
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
function getMaxSumBrute(arr){
let maxSum=0
let startIndex;
let endIndex;
for(let i=0;i<arr.length;i++){
let currentSum=0;
for(let j=i;j<arr.length;j++){
currentSum= currentSum+arr[j];
if(currentSum>maxSum){
maxSum=currentSum
startIndex=i
endIndex=j
}
}
}
return {maxsum:maxSum,index:arr.slice(startIndex,endIndex+1)}
}
function getMaxSum(arr){
let maxSum=arr[0]
let sum=0
let startIndex=0
let endIndex;
for(let i=0;i<arr.length;i++){
sum+=arr[i]
if(sum>maxSum){
maxSum=sum;
endIndex=i
}
if(sum<0){
sum=0
startIndex=i+1
}
}
return {maxsum:maxSum,index:arr.slice(startIndex,endIndex+1)}
}
console.log(getMaxSumBrute([-2,1,-3,4,-1,2,1,-5,4]))
console.log(getMaxSumBrute([5,4,-1,7,8]))
console.log(getMaxSum([-2,1,-3,4,-1,2,1,-5,4]))
console.log(getMaxSum([5,4,-1,7,8]))
JavaScript
INFO