Max Subarray Problem – Kadane’s Algorithm (Dynamic Programming)
Problem The max subarray problem is a problem where you have to find the contiguous subarray (containing at least one number) which has the largest sum, and return the sum. The problem can be found here Test Cases Input Output [-2,1,-3,4,-1,2,1,-5,4] 6 Solution The way to solve this problem is use Kadane’s algorithm: The way that this algorithm works is...