C language free animation tutorial, punch in with me! ๐ Daylight science C language ๐
LeetCode is too hard? Look at the simple questions first! ๐งก 100 cases of introduction to C language ๐งก
Difficult data structure? It doesn't exist! ๐ณ Drawing data structure ๐ณ
LeetCode is too simple? Learn the algorithm! ๐ Writing algorithm in the dead of night ๐
1, Title
1. Title Description
give an integer array nums and an integer
k
k
k. Please return the maximum value of the sum of non empty subsequence elements. The subsequence needs to meet: every two adjacent integers nums[i] and nums[j] in the subsequence, and their subscripts in the original array
i
i
i and
j
j
j satisfied
i
<
j
i < j
I < J and
j
โ
i
โค
k
j - i \le k
jโiโคk.
the subsequence of an array is defined as deleting several numbers in the array (0 numbers can be deleted), and the remaining numbers are arranged in the original order.
sample input: num = [10,2, - 10,5,20], k = 2
sample output: 37
2. Basic framework
- The basic framework code given in the C language version is as follows:
int constrainedSubsetSum(int* nums, int numsSize, int k){
}
3. Original question link
( 1 ) (1) (1) LeetCode 1425. Restricted subsequence sum
2, Problem solving Report
1. Train of thought analysis
first, it's easy to think of the state transition equation
d
p
[
i
]
=
n
u
m
s
[
i
]
+
max
โก
j
=
i
โ
k
i
โ
1
d
p
[
j
]
dp[i] = nums[i] + \max_{j=i-k}^{i-1} dp[j]
dp[i]=nums[i]+j=i − kmaxi − 1 dp[j] this is a time complexity of
O
(
n
k
)
O(nk)
O(nk) algorithm;
we consider
max
โก
j
=
i
โ
k
i
โ
1
d
p
[
j
]
\max_{j=i-k}^{i-1} dp[j]
maxj=i − ki − 1 dp[j], if it can be passed
O
(
1
)
O(1)
O(1), so the total time complexity becomes
O
(
n
)
O(n)
O(n), which is obtained by expanding this formula
m
a
x
(
d
p
[
i
โ
k
]
,
d
p
[
i
โ
k
+
1
]
,
.
.
.
,
d
p
[
i
โ
1
]
)
max( dp[i-k], dp[i-k+1], ..., dp[i-1] )
max(dp[i − k],dp[i − k+1],...,dp[i − 1]), so we can maintain one
(
d
p
[
i
โ
k
]
,
d
p
[
i
โ
k
+
1
]
,
.
.
.
,
d
p
[
i
โ
1
]
)
( dp[i-k], dp[i-k+1], ..., dp[i-1] )
(dp[i − k],dp[i − k+1],...,dp[i − 1]);
the problem is transformed into finding the maximum value in the queue. Since the queue only supports the operation of taking the queue head, the queue head must be the maximum value, that is, it is a monotonically decreasing queue. Add two elements to the queue
i
<
j
i < j
I < J and
d
p
[
i
]
โค
d
p
[
j
]
dp[i] \le dp[j]
dp[i] ≤ dp[j], then
d
p
[
i
]
dp[i]
dp[i] is no better than
d
p
[
j
]
dp[j]
dp[j] is better and can be discarded directly, so the elements in the whole queue must meet the requirements
i
<
j
i < j
When I < J,
d
p
[
i
]
>
d
p
[
j
]
dp[i] > dp[j]
DP [i] > DP [J], that is, it is a monotonically decreasing queue;
iterative calculation
d
p
[
i
]
dp[i]
dp[i]. take
max
โก
i
=
0
n
โ
1
d
p
[
i
]
\max_{i=0}^{n-1} dp[i]
maxi=0n − 1 dp[i] is the final answer.
2. Time complexity
- Any element will only join and leave the team once, and the total time complexity is O ( n ) O(n) O(n). Spread it out evenly, and each operation is O ( 1 ) O(1) O(1).
3. Code explanation
/**************************** Sequence table implementation queue****************************/
#define DataType int
#define maxn 100005
struct Queue {
DataType data[maxn];
int head, tail;
};
void QueueClear(struct Queue* que) {
que->head = que->tail = 0;
}
void QueueEnqueue(struct Queue *que, DataType dt) {
que->data[ que->tail++ ] = dt;
}
void QueueDequeueFront(struct Queue* que) {
++que->head;
}
void QueueDequeueRear(struct Queue* que) {
--que->tail;
}
DataType QueueGetFront(struct Queue* que) {
return que->data[ que->head ];
}
DataType QueueGetRear(struct Queue* que) {
return que->data[ que->tail - 1 ];
}
int QueueGetSize(struct Queue* que) {
return que->tail - que->head;
}
int QueueIsEmpty(struct Queue* que) {
return !QueueGetSize(que);
}
/**************************** Sequence table implementation queue****************************/
int dp[maxn];
int constrainedSubsetSum(int* nums, int numsSize, int k){
struct Queue *q = (struct Queue *)malloc( sizeof(struct Queue) );
int i, max;
max = dp[0] = nums[0]; // (1)
QueueClear(q);
QueueEnqueue(q, 0); // (2)
for(i = 1; i < numsSize; ++i) { // (3)
while(!QueueIsEmpty(q) && i - QueueGetFront(q) > k) // (4)
QueueDequeueFront(q);
dp[i] = nums[i] + dp[ QueueGetFront(q) ]; // (5)
if (dp[ QueueGetFront(q) ] < 0)
dp[i] = nums[i]; // (6)
while(!QueueIsEmpty(q) && dp[ QueueGetRear(q) ] <= dp[i]) // (7)
QueueDequeueRear(q);
QueueEnqueue(q, i); // (8)
if(dp[i] > max)
max = dp[i]; // (9)
}
return max;
}
- ( 1 ) (1) (1) Initialize the value of the 0th element;
- ( 2 ) (2) (2) Insert the position of the 0th element into the queue;
- ( 3 ) (3) (3) Iterate from the first element d p [ i ] dp[i] dp[i]๏ผ
- ( 4 ) (4) (4) Ensure the difference between two adjacent elements โค k \le k โคk๏ผ
- ( 5 ) (5) (5) O ( 1 ) O(1) O(1) calculation d p [ i ] dp[i] dp[i]๏ผ
- ( 6 ) (6) (6) If the previous ones are less than 0, then from i i The number of i must be better at first;
- ( 7 ) (7) (7) Ensure that the queue decreases monotonically;
- ( 8 ) (8) (8) Insert the current element into the queue;
- ( 9 ) (9) (9) Note that you need to traverse here d p [ i ] dp[i] dp[i] statistical maximum;
3, Little knowledge of this topic
generally, the problem of optimizing dynamic programming with monotone queue will involve two out of queue operations
โโโโ
(
1
)
(1)
(1) Ensure that the range is legal;
โโโโ
(
2
)
(2)
(2) Ensure the monotonicity of the queue;
