1031-1040

1031. Maximum Sum of Two Non-Overlapping Subarrays $\star\star$

 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
class Solution {
 public:
  int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
    return max(helper(A, L, M), helper(A, M, L));
  }

 private:
  int helper(vector<int>& A, int l, int r) {
    const int n = A.size();

    vector<int> left(n);
    int sum = 0;

    for (int i = 0; i < n; ++i) {
      sum += A[i];
      if (i >= l) sum -= A[i - l];
      if (i >= l - 1) left[i] = i > 0 ? max(left[i - 1], sum) : sum;
    }

    vector<int> right(n);
    sum = 0;

    for (int i = n - 1; i >= 0; --i) {
      sum += A[i];
      if (i <= n - r - 1) sum -= A[i + r];
      if (i <= n - r) right[i] = i < n - 1 ? max(right[i + 1], sum) : sum;
    }

    int ans = 0;

    for (int i = 0; i < n - 1; ++i) ans = max(ans, left[i] + right[i + 1]);

    return ans;
  }
};

1032. Stream of Characters $\star\star\star$

1033. Moving Stones Until Consecutive $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  vector<int> numMovesStones(int a, int b, int c) {
    vector<int> nums = {a, b, c};

    sort(nums.begin(), nums.end());

    if (nums[2] - nums[0] == 2) return {0, 0};
    return {min(nums[1] - nums[0], nums[2] - nums[1]) <= 2 ? 1 : 2,
            nums[2] - nums[0] - 2};
  }
};

1034. Coloring A Border $\star\star$

1035. Uncrossed Lines $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int maxUncrossedLines(vector<int>& A, vector<int>& B) {
    const int m = A.size();
    const int n = B.size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1
                                        : max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
};

1036. Escape a Large Maze $\star\star\star$

1037. Valid Boomerang $\star$

1038. Binary Search Tree to Greater Sum Tree $\star\star$

1039. Minimum Score Triangulation of Polygon $\star\star$

1040. Moving Stones Until Consecutive II $\star\star$