1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
}
|