Neetcode - Maximum Subarray

Sleep is a function I haven’t called yet.

This problem asks us to find the maximum sum of a contiguous subarray within a given array. The most straightforward (but inefficient) approach is to iterate through all possible subarrays, calculate their sums, and track the maximum. Here's the code for this brute-force solution:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = INT_MIN;
        int n = nums.size();
        int len = n;

        while (len > 0) {
            for (int i = 0; i < n; ++i) {
                if (i + len > n) continue;
                int sum = 0, start = 1, count = 0;
                while (count < len) {
                    sum += nums[i + count];
                    ++count;
                }
                m = max(m, sum);
                sum = 0;
            }
            --len;
        }

        return m;
    }
};

You can see how insufficient the initial approach is. So, let’s try a greedy method instead. In fact, this problem can also be solved using Kadane’s Algorithm, which is inherently a greedy strategy. Interestingly, I had already written a solution based on this algorithm for the Neetcode - Maximum Product Subarray, but I failed to make the connection here. It seems that without truly struggling and internalizing the concept, it doesn’t become second nature.

Anyway, the solution can be written succinctly as follows:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int m = nums[0], curSum = 0;

        for (int num : nums) {
            if (curSum < 0) {
                curSum = 0;
            }
            curSum += num;
            m = max(m, curSum);
        }

        return m;
    }
};

The core idea is: “Forget what we've done—starting now, we build something better.” That’s why, whenever we encounter a negative sum, we abandon it—it won’t lead to a better result moving forward. This concept is quite intriguing, and it makes me wonder if a similar idea could be applied to the Bellman equation in reinforcement learning. It might be worth exploring. We’ll dive deeper into Kadane’s Algorithm in a future post.

Conclusion

There’s much more to say about this. Initially, I approached it using brute force and was completely unaware of the underlying properties of the array. However, this experience taught me an important lesson: always pay attention to the structure and characteristics of the input when tackling a problem.