aboutsummaryrefslogtreecommitdiff
path: root/find_max_non_decr_arr_len.c
blob: 0f218b4f345e575cb92d5c63bcfde1b2ad307603 (plain)
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
}