Как напечатать оптимальный путь от начала в технике динамического программирования

Question

Ниже приведен код для стандартного максимального значения массива, содержащего + ve и -ve числа.Я думаю, что нижеприведенные программы работают правильно.Бот, как мне распечатать оптимальный путь?Удерживая указатель на оптимального родителя, я могу легко напечатать путь в обратном направлении, но как распечатать его в прямом направлении, желательно не ведя слишком много бухгалтерии.

#include <stdio.h>

main()
{
    int array[]={5,-5,3,4,-2};
    int n=5;
    int i;
    int maxsumendingat[n];
    int parent[n];
    int maxsum=-9999; // better way to code?
    int optimallastindex;

    maxsumendingat[0]=array[0];

    for(i=1;i<n;i++)
    {
       if(maxsumendingat[i-1] <= 0)

       { 
           maxsumendingat[i]=array[i]; 
           parent[i]=i; 
       }
      else
      { 
           maxsumendingat[i]=array[i]+maxsumendingat[i-1];  // also keep backtracking info
           parent[i]=i-1;
      }
    }

     // now print results
    for(i=0;i<n;i++) 
    {
      if(maxsum < maxsumendingat[i]) 
      { 
         maxsum=maxsumendingat[i]; 
         optimallastindex=i;
      }
    }

    // now print path. how to print it in fwd direction?
    i=optimallastindex;
    printf("%d ",array[i]);
    while(parent[i]!= i)
    {
        printf("%d ",array[parent[i]]);
        i=parent[i];

    }

}

Answer 1

Просто сохраните обратный путь во временном массиве, а затем повторите этот массив в обратном порядке.

Answer 2

Просто вы можете скопировать родительские элементы в новый массив (или стек), а затем выполнить итерацию массива в обратном порядке или вместо использования родительского элемента next и в своем выражении else сделайте next[i-1] = i.