Алгоритм Кадане можно рассматривать и как жадный, и как DP. Как мы видим, мы сохраняем текущую сумму целых чисел, и когда она становится меньше 0, мы сбрасываем ее до 0 (жадная часть). Это связано с тем, что продолжение с отрицательной суммой намного хуже, чем перезапуск с новым диапазоном. Теперь его также можно рассматривать как DP, на каждом этапе у нас есть 2 варианта: либо взять текущий элемент и продолжить с предыдущей суммой, либо перезапустить новый диапазон. Оба варианта учитываются при реализации.

Array = [-2, -3, 4, -1, -2, 1, 5, -3]
var maxSubArray = 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;
    }
    return maxSum;
};

Этот алгоритм можно рассматривать как простой/тривиальный пример динамического программирования.

Алгоритмическая парадигма:динамическое программирование | На)

function maxSubArraySum(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);
   }
   return max_so_far;
}

Ссылка,