diff options
author | Jack Sangdahl <[email protected]> | 2025-07-08 23:46:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-08 23:46:03 -0600 |
commit | 3be8aa375a6b37ed3d1c83fa153c677ca21da953 (patch) | |
tree | 38d2150890846ce3a1da487ddee78c774be5e37d /find_max_non_decr_arr_len.py | |
parent | c98457f08bd695c1332641d0d482fbaebef87203 (diff) | |
download | leetcode-3be8aa375a6b37ed3d1c83fa153c677ca21da953.tar.gz leetcode-3be8aa375a6b37ed3d1c83fa153c677ca21da953.zip |
2945. find maximum non decreasing array length
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])) |