the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
A:
Kadane's algorithm
Kadane's 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 (in which case its sum is zero) 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:def max_subarray(A): max_ending_here = max_so_far = 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
def max_subarray(A): max_ending_here = max_so_far = A[0] for x in A[1:]: max_ending_here = max(x, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far
Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming.
The runtime complexity of Kadane's algorithm is .
上面写的有点儿乱,
就是DP, 每次加进来的index,就看做maxSum的ending index,看前面的sum value是否是正的。
public class MaxSumSubarray { // Kadane's algorithm public int maxSumSubArray(int[] A) { if (A == null || A.length == 0) return 0; int n = A.length; int[] maxSum = new int[n]; maxSum[0] = A[0]; int result = maxSum[0]; for (int i = 2; i < n; i++) { maxSum[i] = A[i] + Math.max(0, maxSum[i - 1]); result = Math.max(result, maxSum[i]); } return result; } }
No comments:
Post a Comment