牛客网;最长的可整合子数组的长度
链接
作者：Ethan3014
题目.
难度:high
解答：dp[i]表示以s[i]为结尾的字符串的最长可整合字符串。在这里我们用seg来表示有多少个段，其实还可以更简单，判断在m里面的max - min + 1 == len(m)此时就是满足条件的。其实这道题我们根本就不需要dp。
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func convInts(ss []string) []int {
result := make([]int, len(ss))
for i, v := range ss {
res, err := strconv.Atoi(v)
if err != nil {
panic(err)
}
result[i] = res
}
return result
}
func main() {
input := bufio.NewScanner(os.Stdin)
input.Scan()
N, _ := strconv.Atoi(input.Text())
input.Scan()
str := input.Text()
strSplit := strings.Split(str, " ")
number := make([]int, N)
for i := 0; i = 0; j-- {
val := arr[j]
if _, ok := m[val]; ok {
break
}
m[val] = struct{}{}
_, ok1 := m[val+1]
_, ok2 := m[val-1]
if !ok1 && !ok2 {
seg++
} else if ok1 && ok2 {
seg--
}
if seg == 1 && len(m) > dp[i] {
dp[i] = len(m)
}
}
}
return dp[len(arr)-1]
}
复杂度分析
time
O(n**2)
spaceO(n)
执行结果作者：Ethan3014
相关文章
Fredrica
2020-11-10
Orianna
2021-07-12
Bambi
2020-12-28
Miette
2023-06-24
Tanisha
2023-07-20
Jacinthe
2023-07-20
Mathilda
2023-07-20
Tia
2023-07-20
Hellens
2023-07-20
Opal
2023-07-20
Thalia
2023-07-20
Olive
2023-07-20
Dara
2023-07-20
Angie
2023-07-20
Rhea
2023-07-20
Catherine
2023-07-20
Antonia
2023-07-20
Rae
2023-07-20