Javascript Program for Largest Sum Contiguous Subarray

Solution Implementations in Javascript

Approach 1 - Bruteforce: The brute force solution would use nested loops to find ALL of the sub-arrays (a section of an array) in the given array, then compare them to see which of those add up to the highest sum. Here, the issue is that if an array were enormous (say of the order of size 10^8 elements, i.e. ~ 10M), the time complexity of this operation would be catastrophic.

Approach 2 - Kadane’s algorithm: ( a much optimum method) This algorithm was devised by the famous Statistician 'Jay Kadane' who effectively solved the problem in the worst-case time complexity of O(N), i.e. traversing the array only once.

Algorithm
 

• Define two variables, 'presentSum' and 'maxSumYet', both initialised to zero to keep track of the current summed up values and the total max sum so far reached from any of the sub-arrays.
• Now while traversing the sub-array, check the following in each iteration:
  • Update the value of ‘presentSum’ to zero or ‘presentSum’ + arr[i] whichever is greater.
  • Update the 'maxSumYet' value to the updated 'presentSum' or the 'maxSumYet', whichever is greater.
• Finally, return the 'maxSumYet' value after completely traversing the given elements in the array. 
   

Implementation

const largestContiguousSum = (array) => {    let presentSum = 0    let maxSumYet = 0    for(let number of array){        presentSum = Math.max(0, (presentSum + number))        maxSumYet = Math.max(maxSumYet, presentSum)    }    return maxSumYet } You can also try this code with Online Javascript Compiler Run Code

Input

Output

Time Complexity

Since the traversal of all elements in the array takes place just once, therefore worst-case time complexity of O(N), i.e. linear time complexity.

Space Complexity

Since there's no extra space required for storing intermediate values, the space complexity O(1), i.e. constant space complexity.

Even though the time and space complexity is less still, the approach fails to find the largest contiguous sum sub-array when the array comprises only negative integers.

Approach 3 - Dynamic Programming Algorithm: ( efficient method) This dynamic algorithm implementation uses the two essential caveats that this problem has both Over-lapping sub-problems and Optimal substructure. This approach is built on top of Kadane's algorithm that we saw above but would also work in all negative integers present in the array.

Algorithm

• Define two variables, 'presentSum' and 'maxSumYet' both initialised to negative infinity (i.e. the maximum available negative quantifier in the programming language of implementation of the solution, which in this case is JS therefore to 'Number.NEGATIVE_INFINITY') keep track of the current summed up values and the total max sum so far reached from any of the sub-arrays.
• Now while traversing the sub-array check the following in each iteration:
  • Update the value of ‘presentSum’ to arr[i] or ‘presentSum’ + arr[i] whichever is greater.
  • Update the 'maxSumYet' value to the updated 'presentSum' or the 'maxSumYet', whichever is greater.
• Finally, return the 'maxSumYet' value after completely traversing the given elements in the array. 

Implementation

const largestContiguousSum = (array) => {    let presentSum = 0    let maxSumYet = 0    for(let number of array){        presentSum = Math.max(number, (presentSum + number))        maxSumYet = Math.max(maxSumYet, presentSum)    }    return maxSumYet } You can also try this code with Online Javascript Compiler Run Code

Input

Output

Time Complexity

Since the traversal of all elements in the array takes place just once, therefore worst-case time complexity of O(N), i.e. linear time complexity.

Space Complexity

Since there's no extra space required for storing intermediate values, the space complexity O(1), i.e. constant space complexity.

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

FAQs

1. What are the maximum and minimum numerical values that can be used while solving problems in javascript?
   The maximum and minimum numerical values utilised and defined in js are "Number.NEGATIVE_INFINITY" and "Number.POSITIVE_INFINITY".
    
2. What can all approaches be used to solve the problem of finding the largest contiguous sum in a sub-array?
   The three approaches that can be used to solve the problem are:
   Bruteforce
   Kadane’s Algorithm
   Dynamic Programming
    
3. Is Kadane’s algorithm the best approach to solve this problem?
   No, since it wouldn’t give correct results when the whole array is made up only of negative integers.

Key Takeaways

In this article, we took a peek at Javascript solution implementations of finding the largest contiguous sum in a sub-array from a given 1-D array of integers which were solved using “Kadane’s algorithm” and a more effective dynamic programming approach for handling cases when all elements in the array are negative.

Check out this problem - Subarray With 0 Sum 

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.