Classic 150 Interview Questions P53 Maximum Subarray Sum

---

Timeline

Timeline

2025-12-02

init

Dynamic programming, Kadane's algorithm

---

Problem:

P53 Maximum subarray sum

https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-interview-150

Dynamic programming idea: dp[i] represents the maximum subarray sum ending with nums[i], then

$$dp[i] = max{ dp[i-1]+nums[i], nums[i]}$$

That is, if the previous subarray sum plus nums[i] is still smaller than nums[i], then simply start over from nums[i].

#include <vector>
using std::vector;

class Solution {
    public:
	int maxSubArray(vector<int> &nums)
	{
		int i, n = nums.size();
		int max_sum = nums[0];
		vector<int> dp(n);
		dp[0] = nums[0];
		for (i = 1; i < n; i++) {
			dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
			max_sum = std::max(max_sum, dp[i]);
		}
		return max_sum;
	}
};

leetcode hot 100 rewrite

#include <vector>
#include <climits>

using std::vector;

class Solution {
    public:
        int maxSubArray(vector<int> &nums)
        {
                int i, n = nums.size();

                if(n == 0) return 0;

                int max_sum = nums[0];

                // Dynamic Programming
                // dp[i] represents the maximum subarray sum ending with nums[i]
                // dp[i] = max{dp[i-1]+nums[i], nums[i]}
                // That is, if the previous subarray sum plus nums[i] is still smaller than nums[i], then simply start over from nums[i].

                vector<int> dp(n, 0);

                dp[0] = nums[i];

                for (i = 1; i < n; i++) {
                        dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
                        max_sum = std::max(max_sum, dp[i]);
                }

                return max_sum;
        }
};