leetcode

Solution to some Leetcode problems written in C++

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

1911.cpp (1145B)

0 1 // Standard dp 2 class Solution { 3 static long long dp[2][100001]; 4 long long rec(const vector<int> &nums, const int crnt, const bool odd) { 5 if (crnt >= size(nums)) return 0; 6 if (dp[odd][crnt] != -1) return dp[odd][crnt]; 7 long long res = 8 max(rec(nums, crnt + 1, odd), (odd ? -1 : 1) * nums[crnt] + rec(nums, crnt + 1, !odd)); 9 return dp[odd][crnt] = res; 10 } 11 12 public: 13 Solution() { memset(dp, 0xFF, sizeof(dp)); } 14 long long maxAlternatingSum(const vector<int> &nums) { return rec(nums, 0, 0); } 15 }; 16 17 long long Solution::dp[2][100001]; 18 19 // Optimized 1 20 class Solution { 21 public: 22 long long maxAlternatingSum(const vector<int> &nums) const { 23 long long odd = 0, even = 0; 24 for (const int n : nums) { 25 even = max(even, odd + n), odd = even - n; 26 } 27 return even; 28 } 29 }; 30 31 // Optimized 2 32 class Solution { 33 public: 34 long long maxAlternatingSum(const vector<int> &nums) const { 35 long long res = nums[0]; 36 for (int i = 1; i < size(nums); i++) { 37 res += max(nums[i] - nums[i - 1], 0); 38 } 39 return res; 40 } 41 };