LEETCODE***师

1.递归算法（数据大时会超时）

public int massage(int[] nums) {
    if(nums.length==0)
        return 0;
    if(nums.length==1)
    return nums[0];
    if(nums.length==2)
    return Math.max(nums[0], nums[1]);
if(nums.length==3)
    return Math.max(nums[0]+nums[2], nums[1]);

    int result1=nums[nums.length-1]+massage(deleteArr(nums, 2));
int result2=nums[nums.length-2]+massage(deleteArr(nums, 3));
int result=Math.max(result1, result2);
return result;
}
public int[] deleteArr(int[] nums,int n) 
{
    int[]arr=new int[nums.length-n];
    for(int i=0;i<arr.length;i++)
    {
        arr[i]=nums[i];
    }
    return arr;
}

2.改进为动态规划（空间复杂度为O(n)）

public int massage(int[] nums) {
    if(nums.length==0)
        return 0;
    if(nums.length==1)
        return nums[0];
    if(nums.length==2)
        return Math.max(nums[0], nums[1]);
    int result=0;
    int[]dp=new int[nums.length];
    dp[0]=nums[0];
    dp[1]=Math.max(nums[0], nums[1]);
    for(int i=2;i<nums.length;i++)
    {
        dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
    }

    return dp[nums.length-1];
}

3.改进空间复杂度为O(1)

public int massage(int[] nums) {
    int a = 0, b = 0;
    for (int i = 0; i < nums.length; i++) {
        int c = Math.max(b, a + nums[i]);
        a = b;
        b = c;
    }
    return b;
}

作者：sweetiee
链接：https://leetcode-cn.com/problems/the-masseuse-lcci/solution/100-kong-jian-cong-onyou-hua-dao-o1bao-hui-by-swee/
来源：力扣（LeetCode）