动态规划技术中如何从头开始打印最优路径

Question

下面是包含+ve和-ve数字的数组的标准最大和的代码。我认为，下面的程序运行正常。Bot如何打印最优路径？通过保持指向最优父级的指针，我可以很容易地在反向打印路径，但如何在正向打印它，最好不需要保留太多额外的记账。

#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

简单地说，您可以复制新数组(或堆栈)中的父数组，然后按倒序迭代数组，或者在else语句中使用next和next[i-1] = i代替父数组。