diff options
-rw-r--r-- | find_max_non_decr_arr_len.c | 53 | ||||
-rw-r--r-- | find_max_non_decr_arr_len.py | 39 |
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])) |