Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction:
2.
Problem Statement and explanation
3.
Solution Implementations in Javascript
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Javascript Program for Largest Sum Contiguous Subarray

Author dhruv sharma
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

 

Introduction:

 

Finding the largest contiguous sum in a sub-array is a problem that has broad applications when implementing analysis on images or DNA. At the same time, data mining or often in sequencing genomes, is an exciting problem to work on as it has a comprehensive set of applications.

In this article, we will look at a few optimum options and techniques, such as the well-renowned "Kadane's Algorithm" and dynamic programming etc., that can be used to solve this problem. The language of implementation for the solutions would all be in Javascript.

 


Alert Ninjas:  Don’t stop now! Enrol in the Competitive Programming and web development course today and start coding. Learn the art of writing time and space-efficient code, competing in code competitions worldwide, and developing full-stack web applications. 

 


 

Problem Statement and explanation

 

Problem: To find the largest contiguous sum in a sub-array for a given one-dimensional array of integers.

Sample Input: [2, 1, -3, 4, -1, 2, 1, -5, 4]

Sample Output: 6

Explanation: Here the largest contiguous sum in the sub-array -> [4, -1, 2, 1] would be 6. (there are more such largest contiguous sum sub-arrays with a sum = 6 but not greater than that).

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 
}

 

Input

[ -2, -3, 4, -1, -2, 1, 6, -3 ]

 

Output

8

 

 

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 
}

 

Input

[ -100, -1, -3, -5, -2, -6, -100, -4 ]

 

Output

-1

 

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.
 

Live masterclass