leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0053.cpp (667B)

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