首先是做表来支持O(1)查询某个子式的和
枚举+二维压缩成一维需要O(n^2)
在一维上dp，dp方程s[k]=max(s[k-1],0)+a[k]，需要O(n)
总共O(n^3)，考虑规模n<=100，先鄙视一下，然后就做吧

> 不知怎样用dp来做，可以指教一下？

• Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (14) uni 2005-04-26 21:11:57
  • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (42) frkstyc 2005-04-26 21:18:23
    • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (25) uni 2005-04-26 21:21:45
      • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (41) frkstyc 2005-04-26 21:22:31
        • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (7) uni 2005-04-26 21:23:22
          • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (44) frkstyc 2005-04-26 21:25:24
            • Re:请教一下这题最优解的结构，想不通，直接搜过了，不过太慢了 (20) uni 2005-04-26 21:27:29