Find Maximum Subarray Sum in an Array – Kadane’s algorithm

Write a program to find maximum subarray sum in an array. 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 arr[] = { 1, 2, -5, 4, 3, 8 , 5 }

Maximum sum subarray is 20 (4, 3, 8, 5).

Take another array

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

Maximum sum subarray is 19 ( 7, 6, -1, -4, 11).

For solving this problem we are using Kadane’s algorithm. The time complexity of Kadane’s algorithm is O(n).

Subscribe Our Tutorials

Get Latest Updates on Facebook

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

Programming questions on Linked List

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

WebRewrite

About WebRewrite

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