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