3 Line Code using DFS+DP O(n) :D


  • 0
    N
    vector<int> v;
    
    int dfs(int x,vector<int> &visit,vector<int> &dp)
    {
        if(visit[x])    return 0;
        visit[x] = 1;
        dp[x] = 1+dfs(v[x],visit,dp);
        return dp[x];
    }
    
    class Solution {
    public:
        int arrayNesting(vector<int>& nums) {
            v = nums;
            int n = nums.size();
            vector<int> visit(n+1,0);
            vector<int> dp(n+1,0);
            for(int i=0;i<n;i++){
                if(visit[i]==0){
                    int p = dfs(i,visit,dp);
                }
            }
            int maxm = 0;
            for(int i=0;i<n+1;i++){
                maxm = max(maxm,dp[i]);
            }
            return maxm;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.