読者です 読者をやめる 読者になる 読者になる

Maximum Subarray

Recurrence Relation Dynamic Programming Maximum Sum Sequence

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

leetcode.com

Solution

By dynamic programming, we can solve this problem in O(N) time.

Make Recurrence Relation

We can define dp(i) following
dp(i) := max(dp(i - 1) + arr[i], arr[i]

This dp(i) means that it is a max value in all subarrays that range is until position i.

Source Code