2945. Find Maximum Non-decreasing Array Length Hard

1/**
2 * [2945] Find Maximum Non-decreasing Array Length
3 *
4 * You are given a 0-indexed integer array nums.
5 * 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 subarray [3,5] the array will convert to [1,8,6].
6 * Return the maximum length of a non-decreasing array that can be made after applying operations.
7 * A subarray is a contiguous non-empty sequence of elements within an array.
8 *  
9 * Example 1:
10 * 
11 * Input: nums = [5,2,2]
12 * Output: 1
13 * Explanation: This array with length 3 is not non-decreasing.
14 * We have two ways to make the array length two.
15 * First, choosing subarray [2,2] converts the array to [5,4].
16 * Second, choosing subarray [5,2] converts the array to [7,2].
17 * In these two ways the array is not non-decreasing.
18 * And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. 
19 * So the answer is 1.
20 * 
21 * Example 2:
22 * 
23 * Input: nums = [1,2,3,4]
24 * Output: 4
25 * Explanation: The array is non-decreasing. So the answer is 4.
26 * 
27 * Example 3:
28 * 
29 * Input: nums = [4,3,2,6]
30 * Output: 3
31 * Explanation: Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing.
32 * Because the given array is not non-decreasing, the maximum<!-- notionvc: 3447a505-d1ee-4411-8cae-e52162f53a55 --> possible answer is 3.
33 *  
34 * Constraints:
35 * 
36 * 	1 <= nums.length <= 10^5
37 * 	1 <= nums[i] <= 10^5
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/find-maximum-non-decreasing-array-length/
43// discuss: https://leetcode.com/problems/find-maximum-non-decreasing-array-length/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47impl Solution {
48    pub fn find_maximum_length(nums: Vec<i32>) -> i32 {
49        0
50    }
51}
52
53// submission codes end
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn test_2945() {
61    }
62}
63