So the problem is given an array we have to find the maximum possible sum among:
- all nonempty subarrays.
- all nonempty subsequences.
Example: arr = [-1,2,3,-4,5,10]
The maximum subarray sum is comprised of elements at inidices [1-5] Their sum is 2+3+-4+5+10 =16 The maximum subsequence sum is comprised of elements at indices [1,2,4,5] and their sum is [2,3,5,10] = 20
I tried solving this.. But for large arrays (for lengths > 50k) I am getting an error "Abort Called". What is the reason behind this error?! Is it that my code isn't optimised?
function maxSubarray(arr) {
let subsequenceSum = 0
for (let i = 0; i < arr.length; i++) {
if (arr[i] < 0 ) continue
else subsequenceSum += arr[i]
}
if (!subsequenceSum) {
subsequenceSum = Math.max(...arr)
}
const allsubArrays = []
const sumOfEachSubArr = []
for (let i = 0; i < arr.length; i++) {
for (let j = i ; j < arr.length; j++) {
const tempArr = arr.slice(i, j+1)
allsubArrays.push(tempArr)
}
}
// Getting sum of all subarrays
for (let subArr of allsubArrays) {
let sum = subArr.reduce((sum, curVal) => {
return sum + curVal
}, 0)
sumOfEachSubArr.push(sum)
}
let subArraySum = Math.max(...sumOfEachSubArr)
const result = []
result.push(subArraySum,subsequenceSum )
console.log(result)
return result
}