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

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

Get Latest Updates on Facebook

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

Programming questions on Linked List

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

 

 

Kadane’s Algorithm Video Tutorial

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

PHP Code For Finding Maximum Subarray Sum in an Array

 

C Code for Finding Maximum Subarray Sum in an Array

For Reference

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

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.
Tagged , , . Bookmark the permalink.