diff options
Diffstat (limited to 'find_max_non_decr_arr_len.py')
-rw-r--r-- | find_max_non_decr_arr_len.py | 39 |
1 files changed, 39 insertions, 0 deletions
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])) |