Max Sum Contiguous Subarray - The Coding Shala

Home >> Interview Questions >> Max Sum Contiguous Subarray

Max Sum Contiguous Subarray InterviewBit Solution

Problem::

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
Max Sum Contiguous Sub-Array Java Program - The Coding Shala
For example:
Given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
For this problem, return the maximum sum.

Solution

We can solve this problem using Kadane's Algorithm. 

Java Solution::

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int maxSubArray(final List<Integer> A) {
        int curr_max = A.get(0);
        int max = curr_max;
        for(int i=1;i<A.size();i++){
            curr_max = Math.max(A.get(i), curr_max+A.get(i));
            max = Math.max(max, curr_max);
        }
        return max;
    }
}



Other Posts You May Like
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Anti Diagonals - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala