Explaining Maximum Subarray Sum problem with Kadane's Algorithm

There is no alternative of solving dynamic programming related problems in order to get a job in FAANG or big companies and also be a very good programmer. We developers often try to ignore problem solving and focus on only development but we need to remember that in order to solve real life big production problems or optimize something we need to be a very good problem solver. This will help us a lot in solving problems in our day to day career.

So keeping this thing in mind I started solving dynamic programming related problems and in the very beginning I came to know about The Maximum Subarray Sum problem which can be solved easily with Kadane's Algorithm. Today I would like to discuss about this algorithm and solving the problem with it.

At first let us know the description of the problem. It says that

We are given an integer array, we need to find the contiguous subarray that has the largest sum and return that sum. For example: [-2,1,-3,4,-1,2,1,-5,4] is an array. Here the subarray [4,-1,2,1] has the largest sum which is 6.

Now let us see what Kadane's Algorithm says

1. Initialize 2 variables as current_sum to 0 and max_sum to minimum negative value which represent the sum in the current position and maximum sum in that array.
2. Assign the maximum between the current array element and the sum of that element with the current_sum as the current_sum.
3. Assign the maximum between max_sum and the current_sum as the max_sum.
4. Repeat steps 2 and 3 for all the elements of the array.
5. Return the max_sum.

Here I would like to solve the problem in C++ but you have the liberty of choosing any language.

int findMaxSum(vector<int>& nums) {
    int max_sum = INT_MIN;
    int current_sum = 0;

    for(int n:nums) {
        current_sum = max(n, current_sum + n);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

The running time complexity is O(n) as there is a single loop which runs for n times which is the total number of elements in the aaray. In the same time, the space complexity is O(1) since we do not need any external data structures.

Thus we have solved the maximum subarray sum problem using Kadane's algorithm. Now let us see how our approach resembles with a dynamic programming one. In dynamic programming approach, the main problem is divided into a group of smaller problems and each solution of those small problems are utilised again so that they are not needed to be calculated again which is called memoization. Here we have calculated the maximum between each array element and the current sum and assign that maximum as the current sum in that element index. After that we have compared the current and maximum sum in that position and assigned the maximum between them as the maximum sum. Thus in every step we have solved the problem and also used the previously calculated result to be utilized again. Thus we have used dynamic programming approach in our solution.

Understanding and implementing dynamic programming approach is really very hard but with regular practice and a bit hard work we can achieve it. I hope we start solving problems in order to be a very good developer.

Happy coding!!!