转换为动态规划算法

Question

我找到了一个练习，我必须从一定大小的数组的连续元素中找到最大总和。例如，9 个正元素数组中 5 个连续元素的最大和是多少。我读到这最好用动态规划方法进行优化。我是 c++ 的新手，我需要一些帮助将我的代码转换为动态编程算法。希望在这个过程中，我最终会理解它。

这是我的代码：

  int main() 
{
  int arr[9]{10,25,33,14,5,56,27,8,79};
  int array_sums[9]{0};
  for(int i = 0; i < 9; ++i)
  {
    if(i + 4 > 8) { array_sums[i] = 0; }
    else{
      array_sums[i] = arr[i] + arr[i+1] + arr[i+2] + arr[i+3] + arr[i+4];
    }
  }
  int max{0};
  int current_max{0};
  for(int i = 0; i < (sizeof(array_sums)/sizeof(array_sums[0])); ++ i)
  {
    current_max = array_sums[i];
    max = (max < current_max) ? current_max:max;
  }

  cout << "n" << max;
  return 0;
}

感谢您的帮助和时间！

Answer 1

这不是可以通过动态编程改进的程序的好例子。因此，我假设您要查找k连续元素，而不是5连续元素，在本例中是第 8 行而不是

array_sums[i] = arr[i] + arr[i+1] + arr[i+2] + arr[i+3] + arr[i+4];

你会编写这样的代码：

for(int j = 0 ; j<k ; j++)   
    array_sums[i] += arr[i+j];

在这种情况下，您的代码将O(k*n)

现在，您可以使用动态编程来改进代码。代替上面的代码，你可以简单地使用这样的东西：

if(i == 0)
    for(int j = 0 ; j<k ; j++)   
        array_sums[i] += arr[i+j];
else
    array_sums[i] = array_sums[i-1] - arr[i-1] + arr[i+k-1];

在这种情况下，您的代码将O(n)