I want to write a function that determines the largest sum that can be formed by any contiguous subarray in the array.
Input: [-2, 5, -1, 7, -3]
Output: 11 //because of subarray [5, -1, 7]
Input: [1, 2, -10, 20, 1]
Output: 21 //because of [20, 1]
My try
function Max (array) {
let result = Math.max(...array); //in case that there is only one pos. number or all neg.
for (let i = 0; i<array.length; i++) {
for (let j=0; j<array.length; j++) {
if (array.reduce((array[i], array[j]) => array[i], array[j]))
> result)
{result = array.reduce((array[i], array[j]) => array[i], array[j]));
}
}
array.shift[array[i]];
array.pop[array[i]];
}
return result
}
My idea was the following:
Input [1, 2, 3, 4, -5]
--->
----->
-------->
-------------> //check each of the 4 sums against the result
[2, 3, 4, -5, 1]
--->
----->
-------->
-------------> //check each of the 4 sums against the result
[3, 4, -5, 1, 2]
--->
----->
-------->
-------------> //check each of the 4 sums against the result
The basic idea should be correct, yet I couldn't correctly implement it in code. Thanks to everyone reading this or even helping a beginner out!
An alternative solution that I can think with O(n) complexity is:
var array = [-2,1,-3,4,-1,2,1,-5,4];
function maxSumSub(arr){
let curr_sum=arr[0];
let global_sum=arr[0];
for (let i = 1; i < arr.length; i++) {
if(arr[i]>curr_sum+arr[i]) {
curr_sum=arr[i];
}else {
curr_sum=curr_sum+arr[i];
}
if(curr_sum>global_sum) {
global_sum=curr_sum;
}
}
console.log(global_sum);
}
maxSumSub(array);