10/08/2015 Palantir 电面

venomj 发表于 2015-11-5 12:05
肯定有影响啊，负数的可以不累加，但情况并不那么简单
比如：
1  2  3

噢明白了，负数原来可以不加。。

有负数的情况用dp

请问那个负数的follow up 怎么处理呢？

f1371342385 发表于 2015-11-5 12:27
有负数的情况用dp

大神　能详细解释一下吗？

感觉考虑负数的情况比较难。如果矩阵只有一行，那么就是 MaxSubarray的问题，用到DP解决，但是一般2维怎么用DP？

venomj 发表于 2015-11-5 12:05
肯定有影响啊，负数的可以不累加，但情况并不那么简单
比如：
1  2  3

大神可以贴下代码吗？

同求问有负数怎么做

venomj 发表于 2015-11-5 12:05
肯定有影响啊，负数的可以不累加，但情况并不那么简单
比如：
1  2  3

那遍历的时候可以如果发现总结过小于0，还得将标记为已读的变为未读吧

有负数的情况，可以先把负数当成0处理。先把每个岛的大小求出来，并且放到这个岛上的所有位置。然后再扫描一下matrix，遇到有负数的，看是否值得把负数周围的岛链接起来，并更新岛的大小。

venomj 发表于 2015-11-5 12:05
肯定有影响啊，负数的可以不累加，但情况并不那么简单
比如：
1  2  3

非0的都是陆地，题目求的是所有岛屿里的最大值不是所有连续陆地的最大值，所以必须加吧？