4037. Maximum Valid Split Positions II
You are given an integer array nums.
You may remove at most one element from nums. Let arr be the array of remaining elements in their original order, and let m be its length.
A split position i of arr is valid if:
0 <= i < m - 1, andgcd(arr[0..i]) == gcd(arr[i + 1..m - 1]).
An array of length 1 has no valid split positions.
The score of arr is the number of valid split positions in it.
Return the maximum possible score of arr.
Here, gcd(a) denotes the greatest common divisor of all elements in the array a.
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| struct Seg {
int n, log;
vector<int> lg;
vector<vector<int>> st;
Seg(vector<int>& A) {
n = A.size();
lg.resize(n + 1);
for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
log = lg[n] + 1;
st.assign(log, vector<int>(n));
st[0] = A;
for(int k = 1; k < log; k++) {
for(int i = 0; i + (1 << k) <= n; i++) {
st[k][i] = gcd(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
}
int __query(int l, int r) {
if(l > r) return 0;
int k = lg[r - l + 1];
return gcd(st[k][l], st[k][r - (1 << k) + 1]);
}
int query(int l, int r, int skip) {
if(l > r) return 0;
if(skip < l or skip > r) return __query(l, r);
return gcd(__query(l, skip - 1), __query(skip + 1, r));
}
};
class Solution {
int n;
Seg* seg;
int getIndex(int idx, int skip) {
if(skip != -1 and idx >= skip) return idx + 1;
return idx;
}
int getScore(int skip) {
int len = n - (skip != -1);
if(len < 2) return 0;
int g = seg->query(0, n - 1, skip);
int l = 0, r = len - 2;
while(l < r) {
int m = l + (r - l) / 2;
int end = getIndex(m, skip);
if(seg->query(0, end, skip) == g) r = m;
else l = m + 1;
}
int left = l;
if(seg->query(0, getIndex(left, skip), skip) != g) return 0;
l = 0;
r = len - 2;
while(l < r) {
int m = l + (r - l + 1) / 2;
int start = getIndex(m + 1, skip);
if(seg->query(start, n - 1, skip) == g) l = m;
else r = m - 1;
}
int right = l;
if(seg->query(getIndex(right + 1, skip), n - 1, skip) != g) return 0;
return max(0, right - left + 1);
}
public:
int maxValidSplits(vector<int>& nums) {
n = nums.size();
seg = new Seg(nums);
int res = getScore(-1);
for(int skip = 0; skip < n; skip++) {
res = max(res, getScore(skip));
}
return res;
}
};
|
