Given an array with integers, find the largest sum of continuous subarray. This maximum subarray problem was first posed in 1977. Jay Kadane solved it in linear time (O(n)) in 1988. The ApproachThe brute-force way of solving this is to use 2 for-each loops, one inside another, to loop through all combination. However, the linear approach is to use dynamic programming to break down the problem into small ones. Characteristics of dynamic programming:
Thought ProcessThe bigger problem is to find all the combination of contiguous subarrays of a given array A. Among all the combination of contiguous subarrays, find the maximum sum. A smaller problem is to find the maximum sum of contiguous subarray of a given smaller array. When you add an element to a smaller array, "the max of possible sub sequence sum of the bigger array that includes the last element as part of the sum" is either the added element itself, or "the previous max of possible sub sequence sum of the bigger array that includes the previous added element as part of the sum" plus the newly added element. The recursive nature of the solution is: m(i) = the max of possible sub sequence sum of the array that includes the last element as part of the sum For example, let's say A = {-9,-8,17,1,-1,0,1} m(1) = -9 The answer is the max of all possible m(i). max(m(i)) = 18 Code Sinppetclass Test{ References
0 Comments
Leave a Reply. |
Categories
All
Archives
May 2020
|