Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Explanation: [4,-1,2,1] has the largest sum = 6.
Found out that there is an Algorithm and it's called Kadan's Algo, using the dynamic programming paradigm to find the Maximum Sub Array.
Below you will find the short cut to the largest sum contiguous subarray solutions.
First, we will solve the problem using the paradigm Dynamic Programming and then we continue using the divide and conquer approach.
The Algorithmic Paradigm is Dynamic Programming and the Time Complexity is O(n)
Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
We will write a pseudo code, allowing ourselves to represent the implementation of the algorithm we are going to use, the Kadan’s Algorithm. After the pseudo code, we will continue to add the real code of the algorithm which we will run it in the LeetCode Idle.
max_so_far = 0
curr_max = 0
Loop for each element of the array
(a) max_so_far = array
(b) curr_max = array
(c) for each element of the array
curr_max = max of element and sum of curr_max and element
max_so_far = max of max_so_far and curr_max