P-009 maximal subarray

Here is nice twist to an old problem:

Find the subarray with a maximal sum in a circular array of integers. Note the Array A[n] wraps around, so a subarray A[i,j] with i > j is also valid; one counts i, i+1, …, n, 1, …, j.

The first reaction is, why isnt A[1,n] maximal? But that doesn’t work because some elements may be negative integers.

See Also http://en.wikipedia.org/wiki/Maximum_subarray_problem


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: