Dynamic Programming 04

Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Problem link :- click here

Code

import java.util.Scanner;

//	KADANE'S ALGORITHM

public class DynamicProgramming_04
{
	
	static int maxSum(int arr[])
	{
		int cur_sum = arr[0];
		int max_sum = arr[0];
		
		for(int i=1; i<arr.length; i++)
		{
			cur_sum += arr[i];
			
			if(max_sum < cur_sum)
				max_sum = cur_sum;
			if(cur_sum < 0)
				cur_sum = 0;
		}
		
		return max_sum;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		int sum = maxSum(arr);
		System.out.println(sum);
		
		s.close();
	}

}