Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode #53: Maximum Subarray
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if (n==0) {
return 0;
}
vector<int> dp(n);
dp[0] = nums[0];
for (int i=1; i<n; i++) {
dp[i] = nums[i] + max(0, dp[i-1]);
}
return *max_element(dp.begin(), dp.end()); // max in the dp vector.
}
};
// You can easily reduce the space complexity by using 1-2 variables instead of an entire vector/array.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.