leetcode

commit f81d63d0a6b0e03385c36bab57b8e392203bfddd
parent 31e83554ca6ab0ae5cf1c5ea3dd71dd97759ad85
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 18 Jan 2023 18:02:19 +0100

Daily Problem and prep

Diffstat:
A
Problems/0053.cpp
 | 
14
++++++++++++++
A
Problems/0918.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0053.cpp b/Problems/0053.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+  int maxSubArray(vector<int> &nums) {
+    int n = nums.size(), maxi;
+    vector<int> dp(n);
+
+    maxi = dp[0] = nums[0];
+    for (int i = 1; i < n; i++) {
+      dp[i] = nums[i] + max(dp[i - 1], 0);
+      maxi = max(maxi, dp[i]);
+    }
+    return maxi;
+  }
+};
diff --git a/Problems/0918.cpp b/Problems/0918.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+  int maxSubarraySumCircular(vector<int> &nums) {
+    int total, maxSum, curMax, minSum, curMin;
+
+    total = curMax = curMin = 0;
+    maxSum = minSum = nums[0];
+    for (int &n : nums) {
+      curMax = max(curMax + n, n);
+      maxSum = max(maxSum, curMax);
+      curMin = min(curMin + n, n);
+      minSum = min(minSum, curMin);
+      total += n;
+    }
+    return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
+  }
+};
diff --git a/README.md b/README.md
@@ -41,6 +41,7 @@ for solving problems.
 |  0036  |   Medium   | [Valid Sudoku](Problems/0036.cpp)                                                                |
 |  0043  |   Medium   | [Multiply Strings](Problems/0043.cpp)                                                            |
 |  0049  |   Medium   | [Group Anagrams](Problems/0049.cpp)                                                              |
+|  0053  |   Medium   | [Maximum Subarray](Problems/0053.cpp)                                                            |
 |  0054  |   Medium   | [Spiral Matrix](Problems/0054.cpp)                                                               |
 |  0055  |   Medium   | [Jump Game](Problems/0055.cpp)                                                                   |
 |  0056  |   Medium   | [Merge Intervals](Problems/0056.cpp)                                                             |
@@ -206,6 +207,7 @@ for solving problems.
 |  0897  |    Easy    | [Increasing Order Search Tree](Problems/0897.cpp)                                                |
 |  0901  |   Medium   | [Online Stock Span](Problems/0901.cpp)                                                           |
 |  0905  |    Easy    | [Sort Array By Parity](Problems/0905.cpp)                                                        |
+|  0918  |   Medium   | [Maximum Sum Circular Subarray](Problems/0918.cpp)                                               |
 |  0926  |   Medium   | [Flip String to Monotone Increasing](Problems/0926.cpp)                                          |
 |  0931  |   Medium   | [Minimum Falling Path Sum](Problems/0931.cpp)                                                    |
 |  0933  |    Easy    | [Number of Recent Calls](Problems/0933.cpp)                                                      |