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 sub–array in this array is 20. And the sub–array 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).
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
Find Maximum Subarray Sum – Java Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//Find the largest sum contiguous subarray sum import java.util.*; public class MaximumSubarraySum { public static int findMaxSubarraySum(int arr[]) { //Assign first value of an array int maxSum = arr[0]; int sum = arr[0]; //Traverse an array for(int i = 1; i < arr.length; i++) { if(sum < 0) { sum = arr[i]; } else { sum = sum + arr[i]; } //get maxsum maxSum = Math.max(sum, maxSum); } return maxSum; } public static void main(String[] args) { int arr[] = { 1, 2, -5, 4, 3, 8 , 5 }; int result = findMaxSubarraySum(arr); System.out.println(result); } } |
Max Sum Contiguous Subarray InterviewBit Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//InterviewBit Solution public int maxSubArray(final List<Integer> A) { int sum = 0; int max = A.get(0); for(Integer val : A) { if(sum < 0) { sum = val; } else { sum = sum + val; } max = Math.max(sum,max); } return max; } |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
<?php function maxSubArray($arr) { $len = count($arr); $max = 0; $max_so_far = 0; /* Traverse an array */ for ( $i = 0; $i < $len; $i++) { $max = $max + $arr[$i]; /* If max is less than zero then reset it to zero */ if ($max < 0) { $max = 0; } if ( $max > $max_so_far) { $max_so_far = $max; } } return $max_so_far; } $arr = array(1, -3, 2, -5, 7, 6, -1, -4, 11, -23); echo maxSubArray($arr); |
C Program to Find Max-Sum Contiguous Subarray
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> int maxSubArray(int arr[],int len) { int max_so_far = 0; int max = 0; for ( int i = 0; i < len; i++) { max = max + arr[i]; if (max < 0) { max = 0; } if (max_so_far < max) { max_so_far = max; } } return max_so_far; } int main(void) { int arr[] = {1, -3, 2, -5, 7, 6, -1, -4, 11, -23}; int len = sizeof(arr)/sizeof(arr[0]); printf(" Maximum Subarray sum is %d\n ", maxSubArray(arr,len)); return 0; } |
