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.

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".

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

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.

Apart from that, you can use Coding Ninjas Studioto 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 getinterview experiencesfrom people working in big companies.

Live masterclass

Master Python: Discover how PhonePe uses your UPI data

by Ashwin Goyal, Product @ Udaan

28 Jun, 2024

01:30 PM

Roadmap to SDE career at Amazon

by Anubhav Sinha, SDE2 @ Amazon

25 Jun, 2024

01:30 PM

Roadmap to becoming Data Expert at MAANG

by Abhishek Soni, Data Scientist @ Amazon

26 Jun, 2024

01:30 PM

Master Python: Discover how PhonePe uses your UPI data