c++ prefix and suffix sum with 3D-DP array
This solution is inspired from :\nhttps://leetcode.com/problems/largest-plus-sign/discuss/1091541/C%2B%2B-oror-Faster-than-100-oror-Time-O(N2)-oror-DP-oror\n\n\
This solution is inspired from :\nhttps://leetcode.com/problems/largest-plus-sign/discuss/1091541/C%2B%2B-oror-Faster-than-100-oror-Time-O(N2)-oror-DP-oror\n\n\n\n\n````\nclass Solution {\npublic:\n    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {\n      \n        int dp[1000][1000][4] , arr[1000][1000] ;\n        int n = N , ans = 0;\n        memset(dp,0,sizeof(dp));\n        \n        for(int i=0;i<n;++i){                    //prepare array of  1\'s\n            for(int j=0;j<n;++j){\n                arr[i][j] = 1;\n            }\n        }\n        \n        for(auto it : mines){                    //mark given points as  0\'s\n            arr[it[0]][it[1]] = 0;\n        }\n        \n        for(int i=0;i<n;++i){\n            for(int j=0;j<n;++j){\n                if(arr[i][j]){\n                    dp[i+1][j+1][0] = dp[i+1][j][0] + 1;    //left prefix sum\n                    dp[i+1][j+1][1] = dp[i][j+1][1] + 1;    //top  prefix sum\n                }\n            }\n        }\n        \n        for(int i=n-1;i>=0;--i){\n            for(int j=n-1;j>=0;--j){\n                if(arr[i][j]){\n                    dp[i+1][j+1][2] = dp[i+2][j+1][2] + 1;  //down suffix sum\n                    dp[i+1][j+1][3] = dp[i+1][j+2][3] + 1;  //right suffix sum\n                }\n            }\n        }\n        \n        for(int i=1;i<=n;++i){                              //find the max ans\n            for(int j=1;j<=n;++j){\n                int mini = INT_MAX;\n                for(int k=0;k<4;++k){\n                   mini = min(mini,dp[i][j][k]);\n                }\n                ans = max(ans,mini);\n            }\n        }\n        \n        return ans;\n        \n    }\n};\n\n````\n\n
['Dynamic Programming', 'C', 'C++']