Code Destine

Problem Statement

You have given an array of integers, write a program to find out the contiguous subarray (containing at least one number) having the largest sum.

Example 

Input :- [2, 1, -3, -4, 5, 2, 1, 5, -4] 
Output :- 13

Input :- [4, 3, -1, -4, 12, -9, 1, -2, 4]
Output :- 14

Solution

Kadane’s algorithm can be used to solve the maximum subarray problem. In Kadane’s algorithm, we look for all positive contiguous segments of the array and keep track of the maximum sum (max) contiguous segment among all positive segments. Each time when we get a positive sum, we compare it with the maximum sum (max) and if it is greater than max, then we update it.

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.maxSubArray(new int[] {4, 3, -1, -4, 12, -9, 1, -2, 4});
		System.out.println(result);				
	}
	
	/* Solution */    
	public int maxSubArray(int[] nums) {
        int sum = nums[0], max = nums[0];
        for(int i=1; i<nums.length; i++) {
            sum = Math.max(nums[i], nums[i]+sum);
            max = Math.max(sum, max);
        }
        return max;
    }
}

Result

14

Similar Post

1. Positions of Large Groups
2. Find the Duplicate Number in Array
3. Find Common Characters in Array of Strings

That’s all for Maximum Subarray in Java, If you liked it, please share your thoughts in a comments section and share it with others too.