1.
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
主要思路：从终点往回推导。
根据我只能走一步或者走两步这个设定：
假设我离终点只有一步之遥，我只有一种走法：那就是迈一步。
假设我离终点有两步远，我有两种走法：迈两步，或是迈一大步。
好，当n大于2的时候，比方说n=3的时候。
根据我只能走一步，或者走两步这个设定，我走完之后：要么离终点只剩一步（n-2)，要么剩两步（n-1)
我又回到了之前的情况.
我离终点两步时，有两种走法；离终点一步时，有一种走法
所以当n=3，我有1+2=3种走法。
以此类推：n步的走法 = (n-1)步的走法 + (n-2)步的走法（4 = 3+2；5=4+3；6=5+4）
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1: #当n为1时，则只有一种走法。缺乏这个条件语句会导致后续out of index
return 1
result = [0 for i in range(n)] #生成有n个0的list
result[0],result[1] = 1,2 #当n为1时，只有1种走法，n为2时，有两种走法
for i in range(2,n): #
result[i] = result[i-1] + result[i-2]#n的走法为n-1的走法与n-2的走法的合
return result[-1]
另外一种递归写法：
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
if n == 2:
return 2
result1 = self.maxSubArray(n-1)
result2 = self.maxSubArray(n-2)
return result1 + result2
蛮直观，可惜运算时间太长leetcode不给过
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum：
我一开始的思路是把合为正数的子数组存起来，一旦合为负，就从新的正数开始，然而运算速度太拖沓。
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
cursum = maxsum = nums[0]
for num in nums[1:]:
cursum = max(num,cursum + num) #当cursum+num为负数的时候，num如果比它还小，那就不会被存起来，直到遇到正数，直接抛弃掉原来的子数组合，重新开始记录cursum
maxsum = max(cursum, maxsum) #把历史最大数存起来，直到被超越
return maxsum