leetcode

// 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
}