小编eno*_*wiz的帖子

给定一个已经有前k个元素的数组(只包含正整数):a ₁,a ₂,.... a _k. 我需要填充剩余的(n-k)元素(数组总共有n个元素). n 的值约为10 ^ 3且1 <= k <= n. 每个a _i的值是两个数的最小和,使得这两个数的位置之和等于i. 这是伪代码(我的算法):

for i = k + 1 to n
  a[i] = max_value
  for j = 1 to (i / 2)
    a[i] = min(a[i], a[j] + a[i - j])

时间复杂度:O(n ^ 2)

问题:还有其他方法可以更快地完成这项工作吗？
我正在寻找能够找到每个a _i的值小于O(n)的任何数据结构或算法.

P/S:这是我程序中的一个程序,所以我需要尽快完成.