给定一个实数数组A[1..n,1..n],我希望找到子数组B = A[i..j,s..t],其中 1 <= i <= j <= n,而且 1 <= s <= t <= n,使得B中数字的总和最大。能否使用动态规划来解决这个问题?我曾与奥胡斯大学的OR教授交流过,他不知道该如何解决,并表示很难看出它具有最优子结构特性。但是,是否可能?如果是,怎么做?如果不是,为什么?
我已经知道一种运行时间为O(n^3)的算法,通过将其缩减为O(n)复杂度的n(n+1)/2个子问题来解决,但这似乎有点慢。我知道最佳算法将以Ω(n)的时间运行,但我希望可以使用动态编程使其运行时间为O(n^2)。
我已经知道一种运行时间为O(n^3)的算法,通过将其缩减为O(n)复杂度的n(n+1)/2个子问题来解决,但这似乎有点慢。我知道最佳算法将以Ω(n)的时间运行,但我希望可以使用动态编程使其运行时间为O(n^2)。