分治、时间空间的权衡:最大合的连续字串有关问题 (PAT 1007)

分治、时间空间的权衡:最大合的连续字串问题 (PAT 1007)

maxsofa = 0maxendingright = 0for i = [0, n) /* invariant: maxendingright and maxsofar are accurate for x[0..i-1]*/ maxendingright = max(maxendingright + x[i], 0) maxsofar = max(maxsofar, maxendingright)

根据这个思路，写出代码，一遍AC:)

总结：

• 保存状态，避免重复计算：在算法整体框架没有大的优化的情况下，时间和空间的trade-off或许会有奇效。memoization本身就是一种用空间换时间的思想，而DP中用一种方式实现了这种思想。不过不要被DP算法所禁锢。因为，这个trade-off的实现是很多变的，就像这题的第2种算法。
• 分治：它的重要性不必多说了。同样的，DP中有分治的思想，但分治本身也是非常灵活的。
• 数学归纳证明，对算法的设计和正确性佐证很有帮助。话说它也类似于分治的思想呢。