Find Maximum Subarray Sum (Kadane’s algorithm)

In this tutorial, I am going to discuss a very famous interview problem find maximum subarray sum (Kadane’s algorithm).

Given an integer array of N elements, find the maximum sum contiguous subarray (containing at least one element).

For example –

Example 1 –

Input: { 1, 2, -5, 4, 3, 8 , 5 }

Output: 20

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

Example 2 –

Input: {-2, -1}

Output: -1

Example 3 –

Input: { 1, -3, 2, -5, 7, 6, -1, -4, 11, -23}

Output: 19

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

Maximum Subarray Sum

Find Largest Sum Contiguous Subarray Sum

How we can solve this problem efficiently? We can use the Kadane’s algorithm to solve this problem efficiently.

The time complexity for solving this problem using Kadane’s algorithm is O(n).

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

Programming questions on Linked List

Programming video tutorials

Find Maximum Subarray Sum – Java Code

Max Sum Contiguous Subarray InterviewBit Solution

 

 

Largest Sum Contiguous Subarray Sum – Video Tutorial

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

PHP Code to Find Largest Sum Contiguous Subarray Sum in an Array

C Program to Find Max-Sum Contiguous Subarray

Tagged , , . Bookmark the permalink.

About WebRewrite

I am technology lover who loves to keep updated with latest technology. My interest field is Web Development.