1.16 奇安信2024校招笔试真题

1.16.1 无助的产品经理

【题目描述】

在某厂，产品经理同学的工作职责除了给开发同学提需求，还有一件极其重要的事：对产品运营数据做归因分析。

某天，该产品经理同学接到老板要求：根据在过去一段时间内产品的“每日活跃用户数”，统计出最长的增长总天数，也就是把保持增长势头（可以不连续）的天数抽出来，你可能会得到多个新序列，计算最长的那个序列的总天数。

我们把该产品自上线以来“每日的活跃用户数”，都按照顺序放入一个数组，比如：

[1,5,122,34,45,232,342,34]，以这组数据为例，把其中所有的增长子序列罗列出来：

形成了

第一个子序列： [1,5,122]

第二个子序列：[34,45,232,342]

第三个子序列：[1,5,122,232,342]

第四个子序列：[1,5,34,45,232,342]

这四个序列，其中最长的是第四个，所以这个例子中，最长的增长总天数是：6

因为该产品上线时间有十几年了，产品同学数了1个小时，眼都数花了，最后只好放弃，她决定用请开发同学吃饭，来解决这个问题，你能帮帮她吗？

备注：

如果数据集中有多个“最长“增长序列，只需返回其长度即可。

输入样例：

[10,9,2,5,3,6,101,18]

输出样例：

4

说明：

最长增长的子序列为 [2,3,6,101] 或者 [2,5,6,101]或者[2,3,6,18]或者[2,5,6,18]，所以返回长度 4。

【解题思路】

本质上是最长连续序列问题，动态规划、哈希表。

【参考代码】

package main

func lengthOfLIS(nums []int) int {

if len(nums) == 0 {

return 0

}

dp := make([]int, len(nums))

for i := range dp {

dp[i] = 1

}

max := 1

for i := 1; i < len(nums); i++ {

for j := 0; j < i; j++ {

if nums[i]