leetcode

commit 9eb5c5a876e83fa6ddda352dd4a9f06a947ba20b
parent 221c3920e85e34f3fddec4c2310318ee286f1751
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 10 Jan 2024 22:38:44 +0000

1 Random Problem

Diffstat:
A
Problems/1911.cpp
 | 
42
++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 43 insertions(+), 0 deletions(-)
diff --git a/Problems/1911.cpp b/Problems/1911.cpp
@@ -0,0 +1,42 @@
+
+// Standard dp
+class Solution {
+    static long long dp[2][100001];
+    long long rec(const vector<int> &nums, const int crnt, const bool odd) {
+        if (crnt >= size(nums)) return 0;
+        if (dp[odd][crnt] != -1) return dp[odd][crnt];
+        long long res =
+            max(rec(nums, crnt + 1, odd), (odd ? -1 : 1) * nums[crnt] + rec(nums, crnt + 1, !odd));
+        return dp[odd][crnt] = res;
+    }
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    long long maxAlternatingSum(const vector<int> &nums) { return rec(nums, 0, 0); }
+};
+
+long long Solution::dp[2][100001];
+
+// Optimized 1
+class Solution {
+  public:
+    long long maxAlternatingSum(const vector<int> &nums) const {
+        long long odd = 0, even = 0;
+        for (const int n : nums) {
+            even = max(even, odd + n), odd = even - n;
+        }
+        return even;
+    }
+};
+
+// Optimized 2
+class Solution {
+  public:
+    long long maxAlternatingSum(const vector<int> &nums) const {
+        long long res = nums[0];
+        for (int i = 1; i < size(nums); i++) {
+            res += max(nums[i] - nums[i - 1], 0);
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -874,6 +874,7 @@ for solving problems.
 |  1905  |   Medium   | [Count Sub Islands](Problems/1905.cpp)                                                             |
 |  1907  |   Medium   | [Count Salary Categories](Problems/1907.cpp)                                                       |
 |  1910  |   Medium   | [Remove All Occurrences of a Substring](Problems/1910.cpp)                                         |
+|  1911  |   Medium   | [Maximum Alternating Subsequence Sum](Problems/1911.cpp)                                           |
 |  1913  |    Easy    | [Maximum Product Difference Between Two Pairs](Problems/1913.cpp)                                  |
 |  1921  |   Medium   | [Eliminate Maximum Number of Monsters](Problems/1921.cpp)                                          |
 |  1926  |   Medium   | [Nearest Exit from Entrance in Maze](Problems/1926.cpp)                                            |