题意：

给你一张有向无环图，图中每个点都有一个权值，找出一条路径使得路径经过的点权值和最大，输出这条路径。

解法一（记忆化搜索）：

我们记 表示以点 为起点能够获得的最大权值和， 表示以点 为起点能够获得最大权值和的前提下下一个点的编号。
对于 ，显然有

对于 ，显然就是使得 最大的那个

class Solution {
public:
    /*以下是动态分配内存*/
    int** f;
    //f[i][0] 表示以点i为起点开始走能够获得的最大权值和
    //f[i][1] 表示以点i为起点开始走要获得最大权值和的下一个点的编号
    int* val;//val[i] 表示点i的权值
    bool* calc;// calc[i] 记录点i是否计算过
    vector<int>* g;//存图
    void dfs(int u){
        if(calc[u])return;//记忆化搜索
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            dfs(v);
            if(f[u][1]==0||f[v][0]>f[f[u][1]][0]){//选一个权值和最大的后继节点
                f[u][1]=v;
            }
        }
        f[u][0]=f[f[u][1]][0]+val[u];//加上当前节点的权值
        calc[u]=true;//标记已经计算过了
    }
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        int n=potatoNum.size();
        val=new int[n+1]{0};//动态分配内存
        for(int i=0;i<potatoNum.size();i++){
            val[i+1]=potatoNum[i];
        }
        f=new int*[n+1];
        for(int i=0;i<=n;i++){
            f[i]=new int[2]{0};
        }
        calc=new bool[n+1]{false};
        g=new vector<int>[n+1];
        for(int i=0;i<connectRoad.size();i++){
            int u=connectRoad[i][0],v=connectRoad[i][1];
            if(u>v)swap(u,v);
            g[u].push_back(v);//小的指向大的
        }
        for(int i=1;i<=n;i++){
            dfs(i);//每个点为起点遍历
        }
        int t=0;
        for(int i=1;i<=n;i++){
            if(t==0||f[i][0]>f[t][0])t=i;//寻找起点
        }
        string ans;
        stringstream ans_stream;
        while(t){
            ans_stream<<t;
            if(f[t][1]){
                ans_stream<<"-";//记录路径
            }
            t=f[t][1];
        }
        ans_stream>>ans;
        return ans;
    }
};

时间复杂度： ， 表示点的数量， 表示边的数量。由于每个点只会计算一次，程序中求解的过程相当于只遍历了一次整张图，故总的时间复杂度为
空间复杂度： ，使用邻接表存图占 级别的内存，数组都占 级别的内存，故总的空间复杂度为

解法二（拓扑排序）：

由于这是一张有向无环图，我们可以按照倒着的拓扑序从后往前递推上述 数组。
具体的，我们首先对整张图进行拓扑排序，然后再按照倒着的拓扑序进行递推求解，递推的方法根上述一样。
代码：

class Solution {
public:
    int** f;
    //f[i][0] 表示以点i为起点开始走能够获得的最大权值和
    //f[i][1] 表示以点i为起点开始走要获得最大权值和的下一个点的编号
    int* val;//val[i] 表示点i的权值
    bool* calc;// calc[i] 记录点i是否计算过
    vector<int>* g;//存图
    int* incnt;//incnt[i] 表示点i的入度
    int* ord;//ord数组存放拓扑序列
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        int n=potatoNum.size();
        //以下是动态分配内存
        f=new int*[n+1];
        for(int i=0;i<=n;i++){
            f[i]=new int[2]{0};
        }
        val=new int[n+1]{0};
        for(int i=0;i<n;i++){
            val[i+1]=potatoNum[i];
        }
        calc=new bool[n+1]{false};
        g=new vector<int>[n+1];
        incnt=new int[n+1]{0};
        ord=new int[n+1]{0};
        for(int i=0;i<connectRoad.size();i++){
            int u=connectRoad[i][0],v=connectRoad[i][1];
            //建图
            if(u>v)swap(u,v);
            incnt[v]++;
            g[u].push_back(v);
        }
        queue<int> que;
        for(int i=1;i<=n;i++){
            if(!incnt[i])que.push(i);//入度为0的点进队列
        }
        int k=0;
        while(!que.empty()){//拓扑排序
            int u=que.front();
            que.pop();
            ord[++k]=u;
            for(int i=0;i<g[u].size();i++){
                int v=g[u][i];
                if(!--incnt[v]){
                    que.push(v);
                }
            }
        }
        //反转后刚好是倒着的拓扑序，需要从后往前递推
        reverse(ord+1,ord+1+k);
        for(int i=1;i<=k;i++){//开始递推
            int u=ord[i];
            for(int j=0;j<g[u].size();j++){
                if(f[u][1]==0||f[g[u][j]][0]>f[f[u][1]][0]){
                    f[u][1]=g[u][j];
                }
            }
            f[u][0]=f[f[u][1]][0]+val[u];
        }
        int t=1;
        for(int i=2;i<=n;i++){
            if(f[i][0]>f[t][0])t=i;//找起点
        }
        stringstream ans_stream;
        string ans;
        while(t){
            ans_stream<<t;
            if(f[t][1])ans_stream<<"-";
            t=f[t][1];
        }
        ans_stream>>ans;
        return ans;
    }
};

时间复杂度： ，拓扑排序和递推求解的过程相当于分别遍历了一遍整张图，故总的时间复杂度为
空间复杂度： ，使用邻接表存图占 级别的内存，数组都占 级别的内存，故总的空间复杂度为