So the next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.Those who cannot remember the past are condemned to repeat it. — Dynamic ProgrammingHere’s a brilliant explanation on the concept of Dynamic Programming on Quora — Jonathan Paulson’s answer to How should I explain dynamic programming to a 4-year-old?Though there’s more to dynamic programming, we would move forward to understand the Maximum Subarray Problem.Maximum Subarray ProblemThe maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.Maximum Sum Subarray (In Yellow)For example, for the array given above, the contiguous subarray with the largest sum is [4, -1, 2, 1], with sum 6..We would use this array as our example for the rest of this article..Also, we would assume this array to be zero-indexed, i.e..-2 would be called as the ‘0th’ element of the array and so on..Also, A[i] would represent the value at index i.Now, we would have a look at a very obvious solution to the given problem.Brute Force ApproachOne very obvious but not so good solution is to calculate the sum of every possible subarray and the maximum of those would be the solution..We can start from index 0 and calculate the sum of every possible subarray starting with the element A[0], as shown in the figure below..Then, we would calculate the sum of every possible subarray starting with A[1], A[2] and so on up to A[n-1], where n denotes the size of the array (n = 9 in our case)..Note that every single element is a subarray itself.Brute Force Approach: Iteration 0 (left) and Iteration 1 (right)We will call the maximum sum of subarrays starting with element A[i] the local_maximum at index i..Thus after going through all the indices, we would be left with local_maximum for all the indices..Finally, we can find the maximum of these local_maximums and we would get the final solution, i.e..the maximum sum possible..We would call this the global_maximum.But you might notice that this is not a very good method because as the size of array increases, the number of possible subarrays increases rapidly, thus increasing computational complexity.. More details