aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_max_non_decr_arr_len.c53
-rw-r--r--find_max_non_decr_arr_len.py39
2 files changed, 92 insertions, 0 deletions
diff --git a/find_max_non_decr_arr_len.c b/find_max_non_decr_arr_len.c
new file mode 100644
index 0000000..0f218b4
--- /dev/null
+++ b/find_max_non_decr_arr_len.c
@@ -0,0 +1,53 @@
+// 2945. Find Maximum Non-decreasing Array Length
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums'. you can perform any number of
+ * operations, where each operation involves selecting a subarray of the array
+ * and replacing it with the sum of its elements. for example, if the given
+ * array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to
+ * '[1, 8, 6]'. return the maximum length of a non-decreasing array that can be
+ * made after applying the aforementioned operations. a subarray is a contiguous
+ * non-empty sequence of elements within an array
+ */
+
+struct node {
+ int px;
+ int rx;
+ int ml;
+};
+
+int findMaximumLength(int *nums, int numsSize) {
+ struct node *dp = (struct node *)malloc((numsSize + 1) * sizeof(int));
+ int dpl = 1, px = 0;
+ memset(&dp[0], 0, sizeof(struct node));
+ for (int i = 1, j = 0; i <= numsSize; ++i) {
+ px += nums[i - 1];
+ if (j >= dpl)
+ j = dpl - 1;
+ while (j + 1 < dpl) {
+ if (!(px >= dp[j + 1].rx + dp[j + 1].px))
+ break;
+ ++j;
+ }
+ int ml = dp[j].ml + 1, rx = px - dp[j].px;
+ while (1) {
+ if (rx + px >= dp[dpl - 1].rx + dp[dpl - 1].px)
+ break;
+ --dpl;
+ }
+ dp[dpl].px = px;
+ dp[dpl].rx = rx;
+ dp[dpl].ml = ml;
+ }
+ int ans = dp[dpl - 1].ml;
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int n1[] = {5, 2, 2}, n2[] = {1, 2, 3, 4}, n3[] = {4, 3, 2, 6};
+ printf("%d\n", findMaximumLength(n1, ARRAY_SIZE(n1))); // expect: 1
+ printf("%d\n", findMaximumLength(n2, ARRAY_SIZE(n2))); // expect: 4
+ printf("%d\n", findMaximumLength(n3, ARRAY_SIZE(n3))); // expect: 3
+}
diff --git a/find_max_non_decr_arr_len.py b/find_max_non_decr_arr_len.py
new file mode 100644
index 0000000..1621d70
--- /dev/null
+++ b/find_max_non_decr_arr_len.py
@@ -0,0 +1,39 @@
+# 2945. Find Maximum Non-decreasing Array Length
+from itertools import accumulate
+from bisect import bisect_left
+
+"""
+you are given a 0-indexed integer array 'nums'. you can perform any number of
+operations, where each operation involves selecting a subarray of the array
+and replacing it with the sum of its elements. for example, if the given
+array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to
+'[1, 8, 6]'. return the maximum length of a non-decreasing array that can be
+made after applying the aforementioned operations. a subarray is a contiguous
+non-empty sequence of elements within an array
+"""
+
+
+class Solution(object):
+ def findMaximumLength(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n = len(nums)
+ acc = list(accumulate(nums, initial=0))
+ pre = [0] * (n + 2)
+ dp = [0] * (n + 1)
+ i = 0
+ for j, k in enumerate(nums, 1):
+ i = max(i, pre[j])
+ dp[j] = dp[i] + 1
+ l = bisect_left(acc, acc[j] * 2 - acc[i])
+ pre[l] = j
+ return dp[n]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findMaximumLength(nums=[5, 2, 2]))
+ print(obj.findMaximumLength(nums=[1, 2, 3, 4]))
+ print(obj.findMaximumLength(nums=[4, 3, 2, 6]))