4.5 leet 53|70|83

53. Maximum Subarray
    https://leetcode.com/problems/maximum-subarray/
    用两个for循环，更新max的值。

class Solution {
    public int maxSubArray(int[] nums) {        
        int max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++)
        {
            int sum=0;
            for(int j=i;j<nums.length;j++)
            {
                sum=sum+nums[j];
                if(sum>max)
                    max=sum;
            }
        }
        return max;
    }
}

题目建议用divide and conquer，但我想不出怎么divide。
Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]?

https://www.jianshu.com/p/46ea9e851b41

70. Climbing Stairs
    一开始这样写会溢出，会不断计算已经计算过的重复内容。

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

其实这就是一个fibonacci数列，可以这样推进：

class Solution {
    public int climbStairs(int n) {
        int a=1;
        int b=1;
        while(n>0)
        {
            b+=a;//b往后推进一项
            a=b-a;//即a=刚才的b
            n--;
        }
        return a;
    }
}

83. Remove Duplicates from Sorted List
    这题的思路都不用想，非常straight-forward

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        while(head.next!=null)
        {
            if(head.next.val==head.val)
                head.next=head.next.next;
            head=head.next;
        }
        return head;
    }
}
----------
Your input
[1,1,2]
Output
[2]
Expected
[1,2]

我写的是这样的，竟然一把过了？？（嘻嘻开心）Java的链表比c好写耶
但是结果错了，返回的数组只有一个元素。因为我在用head自己做遍历，while结束后，head就变成最后一位了。参照官方solution，应该：

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

不过为什么改动了current之后head也变了呢？