3ms c++


  • 0
    B
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int len=nums.size();
            if (len==0) return 0;
            if (len==1) return nums[0];
            vector<int>f;
            f.resize(len);
            vector<int>g;
            g.resize(len);
            int ans=-INT_MAX;
            int st1=0,ed1=len-2;
            int st2=1,ed2=len-1;
            for(int i=st1;i<=ed1;i++)
            {
                int tmpmax = -1;
                for(int j=st1;j<=i-2;j++)
                    if (f[j]>tmpmax) tmpmax=f[j];
                if (tmpmax==-1) f[i]=nums[i];
                else f[i]=nums[i]+tmpmax;
                if (f[i]>ans) ans=f[i];
            }
            for(int i=st2;i<=ed2;i++)
            {
                int tmpmax = -1;
                for(int j=st2;j<=i-2;j++)
                    if (g[j]>tmpmax) tmpmax=g[j];
                if (tmpmax==-1) g[i]=nums[i];
                else g[i]=nums[i]+tmpmax;
                if (g[i]>ans) ans=g[i];
            }
            return ans;
        }
    };
    

Log in to reply
 

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