Quora店面挂

[nnn]

遇到了老题，
给一个array [1, 1, 2, 2, 2, 2, 2, 3, 3], 返回最大subset sum, subset里不能含有两个连续的数字
比如: {1, 1, 3, 3}, {1}, {2, 2, 2}, {2, 2, 2, 2, 2} 这些都是可以的 {1, 2 ,3}, {2, 2, 3, 3} 这种就不行
最终输出的答案应该是 10, hashmap + dp

各种follow up，也有不用hashmap用bucket sort的解法，python代码附件里有。全部答出来还是被挂了。

[nnn]

楼主想问一下这题bq你是怎么解的。我当时f[i] = i * frequency of i + max(f[:i])
面试官似乎不太认可。。。但是跑了好多个test case也都没毛病。。

dp解法就是跟lc 期死凌 一样，用两个变量dp[0] dp[1]存储选择i的最大值和不选择i的最大值就够了。