# JS | Largest Sum Contiguous Subarray | Kaden’s Algorithm | Dynamic Programing | O(n)

Kadane’s Algorithm can be viewed both as a greedy and DP. As we can see that we are keeping a running sum of integers and when it becomes less than 0, we reset it to 0 (Greedy Part). This is because continuing with a negative sum is way more worse than restarting with a new range. Now it can also be viewed as a DP, at each stage we have 2 choices: Either take the current element and continue with previous sum OR restart a new range. These both choices are being taken care of in the implementation.

Array = [-2, -3, 4, -1, -2, 1, 5, -3]varmaxSubArray= function(nums) {

let sum = 0;

let maxSum = -Infinity;

if(nums.length === 0) return 0;

if(nums.length === 1) return nums[0]

for(let i = 0;i<nums.length;i++){

sum+=nums[i];

maxSum = Math.max(maxSum,sum);

if(sum < 0) sum = 0;

}

returnmaxSum;

};

This algorithm can be viewed as a simple/trivial example of dynamic programming.

**Algorithmic Paradigm: **Dynamic Programming | O(n)

functionmaxSubArraySum(a,size) { let max_so_far = a[0];

let curr_max = a[0];for(let i = 1; i < size; i++) {

curr_max = Math.max(a[i], curr_max + a[i]);

max_so_far = Math.max(max_so_far, curr_max);

}returnmax_so_far;}