Simple C++ Solution || O((2^n)*(n^2)) || Proof by contradiction
Approach :\n1. We go through all possible combinations of n and if any bit in n is set we assume that this person is bad and check if it setisfies the given con
**Approach :**\n1. We go through all possible combinations of ```n``` and if any bit in ```n``` is set we assume that this person is bad and check if it setisfies the given conditions.\n2.  We assume person i is good so he always speaks truth so there are 2 possible contradiction.\n\t\t(i) Person i said that person j is bad but we assume person j is good so, here it contradict.\n        (ii) Person i said that person j is good but we assume person j is bad so, here it contradict.\n\n```\nclass Solution\n{\n    public:\n    int n=0,ans=0;\n    bool isPossible(vector<vector<int>>& arr,vector<bool>& people)\n    {\n        for (int i=0;i<n;i++)\n        {\n            for (int j=0;j<n;j++)\n            {\n                // We assume person i is good so he always speaks truth so there are 2 possible contradiction.\n                \n                //1. Person i said that person j is bad but we assume person j is good so, here it contradict.\n                if (arr[i][j]==0 and people[i] and people[j])\n                    return false;\n                \n                //2. Person i said that person j is good but we assume person j is bad so, here it contradict.\n                else if (arr[i][j]==1 and people[i] and !people[j])\n                    return false;\n            }\n        }\n        // We return true if there is no contradiction\n        return true;\n    }\n    int getGood(int i)\n    {\n        int temp=(__builtin_popcountll(i));\n        return (n-temp);\n    }\n    int maximumGood(vector<vector<int>>& arr)\n    {\n        n=arr.size();\n        // Get all possible combinations and if bit is set assume this person bad.\n        for (int i=0;i<(1<<n);i++)\n        {\n            vector<bool> people(n,true);\n            for (int j=0,temp=i;j<n && temp>0;j++)\n            {\n                if (temp&1)\n                    people[j]=false;\n                temp/=2;\n            }\n            if (isPossible(arr,people))\n                ans=max(ans,getGood(i));\n        }\n        return ans;\n    }\n};\n```\n\n**Time Complexity : ```O((2^n)*(n*2))```**
[]