Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 72246c9

Browse filesBrowse files
javadevjavadev
authored
Improved task 3165
1 parent 99abcf8 commit 72246c9
Copy full SHA for 72246c9

File tree

1 file changed

+104
-102
lines changed
Filter options
  • src/main/kotlin/g3101_3200/s3165_maximum_sum_of_subsequence_with_non_adjacent_elements

1 file changed

+104
-102
lines changed

‎src/main/kotlin/g3101_3200/s3165_maximum_sum_of_subsequence_with_non_adjacent_elements/Solution.kt

Copy file name to clipboard
+104-102Lines changed: 104 additions & 102 deletions
Original file line numberDiff line numberDiff line change
@@ -1,124 +1,126 @@
11
package g3101_3200.s3165_maximum_sum_of_subsequence_with_non_adjacent_elements
22

33
// #Hard #Array #Dynamic_Programming #Divide_and_Conquer #Segment_Tree
4-
// #2024_06_03_Time_1301_ms_(22.22%)_Space_69.8_MB_(100.00%)
4+
// #2024_11_09_Time_109_ms_(100.00%)_Space_87.9_MB_(100.00%)
55

6-
import java.util.stream.Stream
76
import kotlin.math.max
87

98
class Solution {
109
fun maximumSumSubsequence(nums: IntArray, queries: Array<IntArray>): Int {
11-
var ans = 0
12-
val segTree = SegTree(nums)
13-
for (q in queries) {
14-
val idx = q[0]
15-
val `val` = q[1]
16-
segTree.update(idx, `val`)
17-
ans = (ans + segTree.max!!) % MOD
10+
val tree: Array<LongArray?> = build(nums)
11+
var result: Long = 0
12+
for (i in queries.indices) {
13+
result += set(tree, queries[i][0], queries[i][1])
14+
result %= MOD.toLong()
1815
}
19-
return ans
16+
return result.toInt()
2017
}
2118

22-
internal class SegTree(private val nums: IntArray) {
23-
private class Record {
24-
var takeFirstTakeLast: Int = 0
25-
var takeFirstSkipLast: Int = 0
26-
var skipFirstSkipLast: Int = 0
27-
var skipFirstTakeLast: Int = 0
28-
29-
val max: Int
30-
get() = Stream.of(
31-
this.takeFirstSkipLast,
32-
this.takeFirstTakeLast,
33-
this.skipFirstSkipLast,
34-
this.skipFirstTakeLast
35-
)
36-
.max { x: Int?, y: Int? -> x!!.compareTo(y!!) }
37-
.orElse(null)
19+
companion object {
20+
private const val YY = 0
21+
private const val YN = 1
22+
private const val NY = 2
23+
private const val NN = 3
24+
private const val MOD = 1000000007
3825

39-
fun skipLast(): Int? {
40-
return Stream.of(this.takeFirstSkipLast, this.skipFirstSkipLast)
41-
.max { x: Int?, y: Int? -> x!!.compareTo(y!!) }
42-
.orElse(null)
26+
private fun build(nums: IntArray): Array<LongArray?> {
27+
val len = nums.size
28+
var size = 1
29+
while (size < len) {
30+
size = size shl 1
4331
}
44-
45-
fun takeLast(): Int? {
46-
return Stream.of(this.skipFirstTakeLast, this.takeFirstTakeLast)
47-
.max { x: Int?, y: Int? -> x!!.compareTo(y!!) }
48-
.orElse(null)
32+
val tree = Array<LongArray?>(size * 2) { LongArray(4) }
33+
for (i in 0 until len) {
34+
tree[size + i]!![YY] = nums[i].toLong()
4935
}
50-
}
51-
52-
private val seg = arrayOfNulls<Record>(4 * nums.size)
53-
54-
init {
55-
for (i in 0 until 4 * nums.size) {
56-
seg[i] = Record()
36+
for (i in size - 1 downTo 1) {
37+
tree[i]!![YY] = max(
38+
(tree[2 * i]!![YY] + tree[2 * i + 1]!![NY]),
39+
(
40+
tree[2 * i]!![YN] + max(
41+
tree[2 * i + 1]!![YY],
42+
tree[2 * i + 1]!![NY]
43+
)
44+
)
45+
)
46+
tree[i]!![YN] = max(
47+
(tree[2 * i]!![YY] + tree[2 * i + 1]!![NN]),
48+
(
49+
tree[2 * i]!![YN] + max(
50+
tree[2 * i + 1]!![YN],
51+
tree[2 * i + 1]!![NN]
52+
)
53+
)
54+
)
55+
tree[i]!![NY] = max(
56+
(tree[2 * i]!![NY] + tree[2 * i + 1]!![NY]),
57+
(
58+
tree[2 * i]!![NN] + max(
59+
tree[2 * i + 1]!![YY],
60+
tree[2 * i + 1]!![NY]
61+
)
62+
)
63+
)
64+
tree[i]!![NN] = max(
65+
(tree[2 * i]!![NY] + tree[2 * i + 1]!![NN]),
66+
(
67+
tree[2 * i]!![NN] + max(
68+
tree[2 * i + 1]!![YN],
69+
tree[2 * i + 1]!![NN]
70+
)
71+
)
72+
)
5773
}
58-
build(0, nums.size - 1, 0)
74+
return tree
5975
}
6076

61-
private fun build(i: Int, j: Int, k: Int) {
62-
if (i == j) {
63-
seg[k]!!.takeFirstTakeLast = nums[i]
64-
return
77+
private fun set(tree: Array<LongArray?>, idx: Int, `val`: Int): Long {
78+
val size = tree.size / 2
79+
tree[size + idx]!![YY] = `val`.toLong()
80+
var i = (size + idx) / 2
81+
while (i > 0) {
82+
tree[i]!![YY] = max(
83+
(tree[2 * i]!![YY] + tree[2 * i + 1]!![NY]),
84+
(
85+
tree[2 * i]!![YN] + max(
86+
tree[2 * i + 1]!![YY],
87+
tree[2 * i + 1]!![NY]
88+
)
89+
)
90+
)
91+
tree[i]!![YN] = max(
92+
(tree[2 * i]!![YY] + tree[2 * i + 1]!![NN]),
93+
(
94+
tree[2 * i]!![YN] + max(
95+
tree[2 * i + 1]!![YN],
96+
tree[2 * i + 1]!![NN]
97+
)
98+
)
99+
)
100+
tree[i]!![NY] = max(
101+
(tree[2 * i]!![NY] + tree[2 * i + 1]!![NY]),
102+
(
103+
tree[2 * i]!![NN] + max(
104+
tree[2 * i + 1]!![YY],
105+
tree[2 * i + 1]!![NY]
106+
)
107+
)
108+
)
109+
tree[i]!![NN] = max(
110+
(tree[2 * i]!![NY] + tree[2 * i + 1]!![NN]),
111+
(
112+
tree[2 * i]!![NN] + max(
113+
tree[2 * i + 1]!![YN],
114+
tree[2 * i + 1]!![NN]
115+
)
116+
)
117+
)
118+
i /= 2
65119
}
66-
val mid = (i + j) shr 1
67-
build(i, mid, 2 * k + 1)
68-
build(mid + 1, j, 2 * k + 2)
69-
merge(k)
70-
}
71-
72-
// merge [2*k+1, 2*k+2] into k
73-
private fun merge(k: Int) {
74-
seg[k]!!.takeFirstSkipLast = max(
75-
(seg[2 * k + 1]!!.takeFirstSkipLast + seg[2 * k + 2]!!.skipLast()!!),
76-
(seg[2 * k + 1]!!.takeFirstTakeLast + seg[2 * k + 2]!!.skipFirstSkipLast)
120+
return max(
121+
tree[1]!![YY],
122+
max(tree[1]!![YN], max(tree[1]!![NY], tree[1]!![NN]))
77123
)
78-
79-
seg[k]!!.takeFirstTakeLast = max(
80-
(seg[2 * k + 1]!!.takeFirstSkipLast + seg[2 * k + 2]!!.takeLast()!!),
81-
(seg[2 * k + 1]!!.takeFirstTakeLast + seg[2 * k + 2]!!.skipFirstTakeLast)
82-
)
83-
84-
seg[k]!!.skipFirstTakeLast = max(
85-
(seg[2 * k + 1]!!.skipFirstSkipLast + seg[2 * k + 2]!!.takeLast()!!),
86-
(seg[2 * k + 1]!!.skipFirstTakeLast + seg[2 * k + 2]!!.skipFirstTakeLast)
87-
)
88-
89-
seg[k]!!.skipFirstSkipLast = max(
90-
(seg[2 * k + 1]!!.skipFirstSkipLast + seg[2 * k + 2]!!.skipLast()!!),
91-
(seg[2 * k + 1]!!.skipFirstTakeLast + seg[2 * k + 2]!!.skipFirstSkipLast)
92-
)
93-
}
94-
95-
// child -> parent
96-
fun update(idx: Int, `val`: Int) {
97-
val i = 0
98-
val j = nums.size - 1
99-
val k = 0
100-
update(idx, `val`, k, i, j)
101124
}
102-
103-
private fun update(idx: Int, `val`: Int, k: Int, i: Int, j: Int) {
104-
if (i == j) {
105-
seg[k]!!.takeFirstTakeLast = `val`
106-
return
107-
}
108-
val mid = (i + j) shr 1
109-
if (idx <= mid) {
110-
update(idx, `val`, 2 * k + 1, i, mid)
111-
} else {
112-
update(idx, `val`, 2 * k + 2, mid + 1, j)
113-
}
114-
merge(k)
115-
}
116-
117-
val max: Int?
118-
get() = seg[0]?.max
119-
}
120-
121-
companion object {
122-
private const val MOD = 1000000007
123125
}
124126
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.