Kadane’s algorithm is a clever way to solve issue of finding the subarray with the largest sum within a given array in ^O(N) time utilizing dynamic programming practices.

In dynamic programming the idea is to use previous knowledge as much as possible when iterating through a process. This paradigm of programming has various applications, such as financial analysis, data analysis, and image processing as the algorithm is named after a professor of Statistics, Joseph Born Kadane.

Sub-arrays

In order to further explain the process we must first explore the term, sub-array.

A sub-array is a continous array of elements of T inside a bigger array.

To illustrate the concept, let's consider an example. Suppose we have an array of integers: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The maximum subarray sum using Kadane's Algorithm would be 6, corresponding to the subarray [4, -1, 2, 1].

Psuedo-code

So, let’s explain how did Kadane’s algorithm’s logic works. It might resemble sliding window in the sense that we hold two variables that tells us to how to continue with the program. The two variables in question is the maximum_sum_so_far and the current_sum. The algorithm starts with the first element and considers whether including the current element in the subarray would yield a larger sum than the current subarray alone. It updates the current_sum and maximum_sum_so_far accordingly and repeats this process until the entire array is traversed.

Initialize:
max_so_far = INT_MIN
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far

Dynamic Programming Aspect

Dynamic programming is a problem-solving technique that solves complex problems by breaking them down into smaller overlapping subproblems. It optimizes the solution by storing the results of solved subproblems and reusing them when needed, eliminating redundant computations.

In the case of Kadane’s Algorithm we look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive-sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

The dynamic programming aspect comes into play when we compare the current element with the current sum. By considering whether to start a new subarray or extend the current one, we solve smaller subproblems and build the solution for larger subarrays, ultimately efficiently finding the maximum subarray sum.

The Whole Code

    //Without libraries
    int MaxSubArraySum(int[] a, int size)
    {
        int maxSoFar = a[0];
        int maxEndingHere = 0;

        for (int i = 0; i < size; i++)
        {
            maxEndingHere += a[i];

            if (maxEndingHere < 0)
                maxEndingHere = 0;

            else if (maxSoFar < maxEndingHere)
                maxSoFar = maxEndingHere;
        }

        return maxSoFar;
    }
    
    //With Math library
    int MaxSubArraySum_butBetter(int[] a, int size)
    {
        int maxSoFar = a[0];
        int currentMax = a[0];

        for (int i = 1; i < size; i++)
        {
            currentMax = Math.Max(a[i], currentMax + a[i]);
            maxSoFar = Math.Max(maxSoFar, currentMax);
        }

        return maxSoFar;
    }