# Find Largest Sum Contiguous Subarray – Kadane’s algorithm

Write a program to find largest sum contiguous subarray. Given an array of N elements, find the maximum possible sum of a contiguous subarray. An array can contain both positive and negative values.

For example –

Let’s take an array whose values are { 1, 2, -5, 4, 3, 8 , 5 }

The maximum sum of a subarray in this array is 20.  And the subarray is (4, 3, 8, 5).

Find Maximum Subarray Sum in an Array

Take another array –

arr[] = { 1, -3, 2, -5, 7, 6, -1, -4, 11, -23}

The largest sum contiguous subarray  in this array is 19 ( 7, 6, -1, -4, 11).

Subscribe Our Tutorials

For solving this problem we are going to use Kadane’s algorithm. The time complexity for finding largest sum contiguous subarray using kadane’s algorithm is O(n).

Generate prime numbers between 1 to N – Sieve’s Algorithm

NOTE : This code does not handle the cases when all the elements are negative

## Java Program to Find Largest Sum Contiguous Subarray – Kadane’s algorithm

In this video tutorial, I have explained how you can find largest sum contiguous subarray in an array using kadane’s algorithm.

## C Code for Finding Maximum Subarray Sum in an Array

For Reference

https://en.wikipedia.org/wiki/Maximum_subarray_problem