c++ - 转换为动态规划算法

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)