-
Notifications
You must be signed in to change notification settings - Fork 1
/
solution.go
executable file
·109 lines (105 loc) · 7.59 KB
/
solution.go
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package leetcode
import (
"github.com/lomtom/go-utils/assert"
"testing"
)
// 超时
func maxResult1(nums []int, k int) int {
max := func(i, j int) int {
if i > j {
return i
}
return j
}
Max := func(slices []int) int {
if len(slices) == 0 {
return 0
}
m := slices[0]
for index := range slices {
m = max(slices[index], m)
}
return m
}
l := len(nums)
dp := make([]int, l)
dp[0] = nums[0]
for i := 1; i < l; i++ {
dp[i] = Max(dp[max(i-k, 0):i]) + nums[i]
}
return dp[l-1]
}
// 执行耗时:91 ms,击败了94.87% 的Go用户
// 内存消耗:8.4 MB,击败了53.85% 的Go用户
func maxResult(nums []int, k int) int {
l := len(nums)
dp := make([]int, l)
dp[0] = nums[0]
// 单调递减队列
queue := []int{0}
for i := 1; i < l; i++ {
// 1. 出队 (拿到队头，即最大值)
if queue[0] < i-k {
queue = queue[1:]
}
// 2. 转移
dp[i] = dp[queue[0]] + nums[i]
for len(queue) > 0 && dp[i] >= dp[queue[len(queue)-1]] {
// 出队，直到队列元素大于dp[i]
queue = queue[:len(queue)-1]
}
// 3. 入队
queue = append(queue, i)
}
return dp[l-1]
}
func TestMaxResult(t *testing.T) {
type input struct {
nums []int
k int
}
collections := []struct {
input
output int
}{
{
input{
[]int{100, -1, -100, -1, 100},
2,
},
198,
},
{
input{
[]int{1, -1, -2, 4, -7, 3},
2,
},
7,
},
{
input{
[]int{10, -5, -2, 4, 0, 3},
3,
},
17,
},
{
input{
[]int{1, -5, -20, 4, -1, 3, -6, -3},
2,
},
0,
},
{
input{
[]int{-5582, -5317, 6711, -639, 1001, 1845, 1728, -4575, -6066, -7770, 128, -3254, 7281, 3966, 6857, 5477, 8968, -1771, 9986, -6267, 9010, -764, 8413, -8154, 1087, -1107, 4183, 3033, 58, 659, 4625, 2825, 5031, 6811, 5657, 3229, 8597, -5772, 8869, 5723, 2960, 4040, 7222, 4841, -1014, 581, -2830, 3881, -3800, 577, -7396, -611, -6944, 8461, 3294, 6297, 9713, -2246, -3441, 3831, -5754, 6716, 6040, -6715, 5763, 8611, 5412, -7630, 6216, 260, 2595, 6852, -8956, 2101, 6722, 1579, 3820, 7827, -3369, 7144, 1974, 7310, -5369, -6755, 3010, 5789, 1563, -3330, 5373, -2770, 4503, -4065, 8177, -3333, -4726, -2131, 2763, 9012, -4755, 2382, 3642, -5284, -7174, -9815, 6392, 9729, -1943, -8749, 5343, 1036, 8508, 1484, 919, 4225, 3733, 8036, -6346, -2088, 475, 9378, 4271, -5906, 9327, 9399, -1582, 3845, 3499, -8912, -4671, -1143, -5081, -1621, -1287, 5995, 4963, 5071, 5118, -1966, -6249, 663, -2296, -8148, -4668, -6919, 334, -6609, 2888, -4161, 118, -1867, 5629, 8588, -5325, -7853, -4868, -1487, -6544, -9697, -7038, 6422, -5545, 3376, -8656, 8800, -7698, -2928, 2279, -9739, 4198, 6236, -9087, 9010, -9894, 2145, 7353, -92, 3205, 5431, 5913, 1619, -250, 4728, -7164, -5619, -4721, -9284, -9645, 146, 7131, -6501, 4261, 2016, 2880, 4944, -8768, -6339, -3574, 539, 4633, 9188, 7227, -1549, 9271, 7110, 5706, 4968, -1275, 5545, -5844, -1985, 9560, 1560, 4630, 3169, 6076, -9433, 7007, 9927, -8385, -4557, -114, 9543, 2884, 8978, -6447, 3664, -7499, -4643, -5993, -5321, 3250, -2945, 6216, -1606, 5569, 7326, -6027, 9723, -6997, -543, -8298, -4647, 2563, 1493, 9574, 1087, -9433, -7749, -7159, -2682, 6626, 2787, -2845, -7907, -223, -8142, -5403, -3460, -2534, 5289, 999, 9404, -1958, 641, 4669, -2892, -2921, -7001, -1403, -2353, -7976, -5885, 4958, -8117, 8785, -654, 5918, 5533, 8704, 5827, -7478, -3696, 2640, 1612, -500, 5694, -1973, 5308, 5272, 3358, 9190, 4648, -7836, 658, -3407, 6733, 1061, -2010, -2707, -1920, 1272, 3944, -6537, -6090, -7429, -640, 836, 1904, -4031, 814, -1886, 8040, -8312, -9407, -1395, -9944, -2074, -6814, 2672, 1360, 8990, 5465, -2131, 3838, 799, -3472, 1086, -583, 6302, 3032, 9138, -7778, 4538, -5337, 2087, 2870, -3005, 3401, 122, -819, -8074, 9630, -698, 5326, 2650, -9355, 6487, 3801, -3209, 8293, 662, -8318, -7863, -3814, -2557, -5685, -7952, 6224, -7010, 2935, 5557, -1287, 9528, -9218, -5108, -2085, 17, 4870, -8686, -8854, -9657, 8848, -1883, -4535, 83, 9711, 4593, -3440, -6938, 3407, -6894, -6213, -883, 4552, -731, 1485, -7740, -3300, 3897, -7629, -4076, 7589, 3142, -1010, 2466, -592, -391, 3961, -7049, 7654, 5758, 6983, 6048, -4369, -5878, 3756, 2940, 9149, 8625, 8937, 5706, 6658, 9213, -5226, 284, -4524, -1577, -5296, 6423, 9977, -1805, 5462, 7587, 476, -6424, 976, -3925, 8819, 1821, 3603, -842, -9618, -7130, -6253, 2562, -7596, 3522, 6282, -3801, -3896, 6924, 441, 5944, 8535, 1253, -6154, 6872, -9548, -5358, 1604, 9593, -9256, -701, 1023, -1446, -1307, -6809, 9542, 3673, 1813, 8717, -6847, -5289, 5222, -7266, 4231, 218, -9633, -4696, 5494, 9681, 1173, -4606, 2174, -1155, -8595, -3640, -6550, -7003, 4244, -2543, 5241, 2831, 2690, 8950, -6609, -9724, 7562, -4096, 8878, 9962, 7179, -1170, 7826, -146, -2759, -5249, 253, 6206, 3205, -7708, 9448, 4622, 9260, -2853, 2486, 122, -8880, -769, -8922, 648, 7358, -6503, -6382, -4260, 3988, -5107, -6363, 2415, 8563, -9070, -5026, 2078, -2558, -2027, -7489, -4978, 5024, 4155, -9737, -221, 9930, -9472, 1052, -268, 6221, 2726, -1310, -8708, 3482, -5488, -6506, 5389, -7048, 553, -886, 2752, 85, -3938, 5940, -5112, 5855, -7295, 3735, 2657, 3269, 6231, 4771, 3229, -2009, -5748, 7256, 746, -4301, 752, -241, -6151, -2390, 9911, 825, -7679, -4960, -7224, -2739, -566, -5770, 6774, 6243, 3166, -783, -4303, -9016, 5555, -1866, -536, 8872, -3927, 4269, -3807, 1933, 9972, 981, 9256, 6857, -208, 3645, -3725, 5961, 1105, 6320, -4702, -8419, -4904, -4935, 8378, -2994, 5831, 5296, 4730, -9170, -4229, -3911, -160, 8757, -5301, -3775, 1121, 9434, -9880, 2689, 2340, -7879, 3667, -5219, -6116, -1670, 7595, 6900, 3990, 4444, 6385, -2924, 8968, -2673, -6182, 7503, 5209, 6030, 802, -3464, 1922, -8187, 1617, 4769, -4866, -3518, 5830, 3862, -7512, 5236, -5164, 6324, -5107, 6864, -7364, -1375, 5762, -275, 4975, -7448, 5719, -3162, -1546, -2776, -9411, -1845, -4913, -3474, 2550, 5643, -5527, 2946, 7158, 1938, 5125, -8015, 2475, -1461, -4900, -5151, -4031, 9362, 8571, 9815, -8438, -6519, 1980, -8031, 9615, 7079, -3573, -883, 4217, 1079, 5918, 1767, 8670, -5651, -6625, 1057, 7897, -7104, -4186, 851, -6333, -4108, -3250, 7899, 9628, -6904, -3939, 4587, 1227, 3813, -7449, -7692, -8098, -9813, 8862, -2888, -1048, -3564, 3074, 1437, -2291, 3974, 3164, 4921, -8958, 9007, -3938, 2042, 7454, -910, -998, -4450, -1103, -237, 8182, -1391, -4255, -3482, -2918, 4053, 2280, -7403, 4319, -9457, 7157, -6315, -7533, 6309, 2211, -9145, 443, 4255, -8847, -5557, -9089, 1752, -5784, -2399, -8296, -8400, 8170, 4628, -4583, 937, -7067, -3503, -549, -1194, 1576, 5004, -6963, -8837, 5567, 870, 3954, 5489, -8949, -7673, 8542, -9040, -7689, -4171, -889, 5552, -6836, -4393, 513, 3177, 6664, -5646, 2492, 9421, -342, 2570, 8816, 2869, -6820, -3389, -1903, -3332, 138, 6618, 293, -9130, 3503, -2327, -9728, 7632, 5881, 540, 9678, -7629, 8804, -2816, 7205, 7473, -5518, 7311, 3457, 9066, -1224, 2097, 7857, 6612, 186, 6759, -4516, -3491, -8268, -8928, -7412, 7162, 6274, 5463, 2157, -4131, -7061, -8476, -5584, 7300, -4348, -5940, -8592, -302, -5817, 3151, -4124, 1694, -5114, -3252, -2319, -2157, -293, 7724, -5673, 6105, 9535, 4333, 6353, 1290, 8710, -5035, 8995, -5865, 9746, 4708, -6387, -8937, 3096, -9716, -7124, 2531, -660, -4619, -8035, 3747, -7821, 8793, -727, 8242, 4957, -7175, 4064, -9911, 4995, 9725, 1634, -4275, 788, -4920, 3831, -3525, -4467, 2909, -1200, 5377, -4905, -3077, -1763, 4443, -3518, 3134, -5595, 5409, 5943, 6757, 3485, 2883, -9261, -7221, 654, 2001, -926, 7840, -5568, 2715, -7053, -2082, -2005, 7607, -9511, 7545, 7564, 2380, -7257, 1449, -3918, -3240, -1928, -6555, -4784, 1550, 2745, -5316},
56,
},
2354241,
},
}
s := assert.NewAssert(t)
for index := range collections {
s.Equal(collections[index].output, maxResult(collections[index].input.nums, collections[index].input.k))
}
}