leetcode

commit 4342f7511e21103b79c9e605241ae41f134cee85
parent 141176754da437857bc4f537c6d66b9b1d5a5c07
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Jan 2023 21:29:08 +0100

Data Structure I: Day 1

Diffstat:
M
Problems/0053.cpp
 | 
12
++++++++++++
M
Problems/0217.cpp
 | 
9
+++++++++

2 files changed, 21 insertions(+), 0 deletions(-)
diff --git a/Problems/0053.cpp b/Problems/0053.cpp
@@ -1,3 +1,4 @@
+// memorization approach
 class Solution {
 public:
   int maxSubArray(vector<int> &nums) {
@@ -12,3 +13,14 @@ public:
     return maxi;
   }
 };
+
+// optimized, memorize only the previous value
+class Solution {
+public:
+  int maxSubArray(vector<int> &nums) {
+    int n = nums.size(), maxi, prev;
+    maxi = prev = nums[0];
+    for (int i = 1; i < n; i++) maxi = max(maxi, prev = nums[i] + max(prev, 0));
+    return maxi;
+  }
+};
diff --git a/Problems/0217.cpp b/Problems/0217.cpp
@@ -10,3 +10,12 @@ public:
     return false;
   }
 };
+
+// Fun oneliner
+class Solution {
+public:
+  bool containsDuplicate(vector<int> &nums) {
+    return nums.size() > unordered_set<int>(nums.begin(), nums.end()).size();
+  }
+};
+