Maximum subarray problem: Difference between revisions

Revision as of 02:42, 30 March 2008

Revision as of 03:03, 30 March 2008

Line 1:

In [[computer science]], the '''maximum subarray problem''' for a given one-dimensional [[array]] of numbers is to find the contiguous subarray with maximum sum. The problem was first posed by [[Ulf Grenander]] of [[Brown University]] in 1977, as a simplified model for [[maximum likelihood]] estimation of patterns in digitized images. A linear time algorithm to solve it was found soon afterwards by [[Jay Kadane]] of [[Carnegie-Mellon University]], and first published by {{harvtxt|Bentley|1984}}.

'''Kadane's Algorithm''' finds the Sub-[[Array]] of any size with Maximum sum.

The algorithm consists of a scan through the array values, computing at each position the maximum subarray ending at that position. This subarray is either empty or consists of one more element than the maximum subarray ending at the previous position. Thus, the problem can be solved with the following code, expressed here in [[Python (programming language)|Python]]:

for example of Array is like

{| class="wikitable"

|-

| 1

| -2

| 3

| 4

| -10

| 6

|}

then sub-array will be

{| class="wikitable"

|-

| 3

| 4

|}

<source lang="python">

== ALGORITHM ==

def max_subarray(A):

max_so_far = max_ending_here = 0

for x in A:

max_ending_here = max(0, max_ending_here + x)

max_so_far = max(max_so_far, max_ending_here)

return max_so_far

</source>

Similar problems may be posed for higher dimensional arrays, but their solution is more complicated.

<pre>

INPUT

A===>Array In which SubArray To Find

n===>Size of Array

pk===>Pointer to k which give lower index of sub-array

pl===>Pointer to l which give upper index of sub-array

</pre>

Returns the sum of sub-array

==References==

<pre>

*{{citation

int Kadane(int* A,int n,int* pk,int* pl)

| first = Jon | last = Bentley

{

| title = Programming pearls: algorithm design techniques

*pk=0;

| journal = [[Communications of the ACM]]

*pl=0;

| volume = 27 | issue = 9 | year = 1984 | doi = 10.1145/358234.381162 | pages = 865–873}}.

int s=1<<31;

int t=0;

int i,j=0;

for(i=0;i<n;i++)

{

t=t+A[i];

if(t>s)

{

*pk=j;

*pl=i;

s=t;

}

if(t<0)

{

t=0;

j=i+1;

}

print(A,n,i,j,*pk,*pl,s,t);

}

return s;

}

</pre>

== External links ==

Line 63 ⟶ 27:

[[Category:Optimization algorithms]]

[[Category:Articles with example Python code]]