c - 如何在动态规划技术中从头开始打印最佳路径

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

只需将反向路径存储在一个临时数组中，然后向后迭代该数组。