Conversion to Dynamic Programming alg

Question

I found an exercise where I have to find the maximum sum from contiguous elements of an array, of a certain size. For example, what is the maximum sum of 5 contiguous elements, of an array of 9 positive elements. I read that this is best optimized with a Dynamic Programming approach. I am new to c++ and I would like some help to convert my code to Dynamic Programming alg. Hopefully in the process I will finally understand it.

Here is my code:

  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;
}

Thank you for your help and your time!

Answer 1

This is not a good example of a program that can be improved by Dynamic Programming. So instead of 5 contiguous elements, I assume you want to find k contiguous elements, in this case in your line 8 instead of

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

you would code something like this:

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

In this case, your code would be O(k*n)

now you could use dynamic programming to improve your code. Instead of the above code, you could simply use something like this:

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];

And in this case your code would be O(n)