2263 solved.

liuyubobobo · liuyubobobo · commit 260a4d52c5d5 · 2022-06-09T16:56:14.000-07:00
diff --git a/2001-2500/2263-Make-Array-Non-decreasing-or-Non-increasing/cpp-2263/CMakeLists.txt b/2001-2500/2263-Make-Array-Non-decreasing-or-Non-increasing/cpp-2263/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_2263)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_2263 main.cpp)
diff --git a/2001-2500/2263-Make-Array-Non-decreasing-or-Non-increasing/cpp-2263/main.cpp b/2001-2500/2263-Make-Array-Non-decreasing-or-Non-increasing/cpp-2263/main.cpp
@@ -0,0 +1,77 @@
+/// Source : https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/
+/// Author : liuyubobobo
+/// Time   : 2022-06-09
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// DP + Basic Optimization
+/// Time Complexity: O(n * maxv)
+/// Space Complexity: O(n * maxv)
+class Solution {
+
+public:
+    int convertArray(vector<int>& nums) {
+
+        int n = nums.size(), maxv = *max_element(nums.begin(), nums.end());
+
+        int res1 = solve(n, nums, maxv);
+
+        reverse(nums.begin(), nums.end());
+        int res2 = solve(n, nums, maxv);
+
+        return min(res1, res2);
+    }
+
+private:
+    int solve(int n, const vector<int>& nums, int maxv){
+
+        vector<int> dp(maxv + 1), premin(maxv + 1);
+        for(int v = 0; v <= maxv; v ++){
+            dp[v] = abs(nums[0] - v);
+            if(v) premin[v] = min(premin[v - 1], dp[v]);
+            else premin[v] = dp[v];
+        }
+
+        for(int i = 1; i < n; i ++){
+            vector<int> tdp(maxv + 1);
+            for(int v = 0; v <= maxv; v ++)
+                tdp[v] = premin[v] + abs(nums[i] - v);
+
+            premin[0] = tdp[0];
+            for(int v = 1; v <= maxv; v ++) premin[v] = min(premin[v - 1], tdp[v]);
+            dp = tdp;
+        }
+        return *min_element(dp.begin(), dp.end());
+    }
+};
+
+
+int main() {
+
+    vector<int> nums1 = {3,2,4,5,0};
+    cout << Solution().convertArray(nums1) << '\n';
+    // 4
+
+    vector<int> nums2 = {2,2,3,4};
+    cout << Solution().convertArray(nums2) << '\n';
+    // 0
+
+    vector<int> nums3 = {0};
+    cout << Solution().convertArray(nums3) << '\n';
+    // 0
+
+    vector<int> nums4 = {0,2,8,0,3};
+    cout << Solution().convertArray(nums4) << '\n';
+    // 8
+
+    vector<int> nums5 = {4,2,6,7};
+    cout << Solution().convertArray(nums5) << '\n';
+    // 2
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2106,7 +2106,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2260 | [Minimum Consecutive Cards to Pick Up](https://leetcode.com/problems/minimum-consecutive-cards-to-pick-up/) | [无] | [C++](2001-2500/2260-Minimum-Consecutive-Cards-to-Pick-Up/cpp-2260/) | | |
 | 2261 | [K Divisible Elements Subarrays](https://leetcode.com/problems/k-divisible-elements-subarrays/) | [无] | [C++](2001-2500/2261-K-Divisible-Elements-Subarrays/cpp-2261/) | | |
 | 2262 | [Total Appeal of A String](https://leetcode.com/problems/total-appeal-of-a-string/) | [无] | [C++](2001-2500/2262-Total-Appeal-of-A-String/cpp-2262/) | | |
-| | | | | | |
+| 2263 | [Make Array Non-decreasing or Non-increasing](https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/) | [无] | [C++](2001-2500/2263-Make-Array-Non-decreasing-or-Non-increasing/cpp-2263/) | | |
 | 2264 | [Largest 3-Same-Digit Number in String](https://leetcode.com/problems/largest-3-same-digit-number-in-string/) | [无] | [C++](2001-2500/2264-Largest-3-Same-Digit-Number-in-String/cpp-2264/) | | |
 | 2265 | [Count Nodes Equal to Average of Subtree](https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/) | [无] | [C++](2001-2500/2265-Count-Nodes-Equal-to-Average-of-Subtree/cpp-2265/) | | |
 | 2266 | [Count Number of Texts](https://leetcode.com/problems/count-number-of-texts/) | [无] | [C++](2001-2500/2266-Count-Number-of-Texts/cpp-2266/) | | |
