class Solution {
public:
    int rob(vector<int>& nums) {
        auto n=nums.size();
        if(nums.empty())
            return 0;
        vector<vector<int>> dp(n,vector<int>(n,0));

        for(int i=0;i<n;++i)
            dp[i][i]=nums[i];

        for(int i=n-2;i>=0;--i)
            for(int j=i+1;j<n;++j)
            {
                auto a=i+2<=j?dp[i+2][j]+nums[i]:0;
                auto b=i<=j-2?dp[i][j-2]+nums[j]:0;
                auto c=max(a,b);
                auto d=max(dp[i+1][j],dp[i][j-1]);
                dp[i][j]=max(d,c);
            }

        return dp[0][n-1];
    }
};