leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0053.cpp (667B)

0 // memorization approach 1 class Solution { 2 public: 3 int maxSubArray(vector<int> &nums) { 4 int n = nums.size(), maxi; 5 vector<int> dp(n); 6 7 maxi = dp[0] = nums[0]; 8 for (int i = 1; i < n; i++) { 9 dp[i] = nums[i] + max(dp[i - 1], 0); 10 maxi = max(maxi, dp[i]); 11 } 12 return maxi; 13 } 14 }; 15 16 // optimized, memorize only the previous value 17 class Solution { 18 public: 19 int maxSubArray(vector<int> &nums) { 20 int n = nums.size(), maxi, prev; 21 maxi = prev = nums[0]; 22 for (int i = 1; i < n; i++) 23 maxi = max(maxi, prev = nums[i] + max(prev, 0)); 24 return maxi; 25 } 26 };