Problem statement Given an array of integers, find a sub array in it with largest sum. This problem is solved using Kadane's algorithm. For example, for array {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3} maximum sum sub array will be {4,6,-1,2,-7,13} with sum = 17 Analysis At every number in array, we need to take decision on two possibilities: 1. Number is included in already existing sub array and it increases the sum. 2. Number is not included as it makes the sum negative and adding this will make all subsequent addition less than what we already have.
Read full article from Algorithms and Me: Dynamic programming : Contiguous sub array with largest sum
No comments:
Post a Comment