Problem 1
寻找最大的连续子数组
考察点：动态规划的思路
Description：
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [0]
Output: 0
Example 4:
Input: nums = [-1]
Output: -1
Example 5:
Input: nums = [-2147483647]
Output: -2147483647
Constraints:
1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
（1）自己的想法
借鉴网上的做法，如果当前的求和结果为负数，则舍弃当前的结果，因为加和的结果不可能最大，在一次搜索的过程中保存更新计算结果与最大值，由于之前的程序设计的两个值都是0使得出现数组中都是负数的情况下结果不AC
下面讲讲动态规划的思路，在搜索的过程中，局部最优结果选择当前遍历到的数组值，而全局结果结合局部结果取得最优值，代码如下：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l=len(nums)
if l==0:
return []
else:
maxLocal=maxglobal=nums[0]
for i in range(1,l):
maxLocal=max(nums[i], nums[i] + maxLocal)
maxglobal=max(maxglobal, maxLocal)
return maxglobal
Problem 2
不连续的房屋盗窃问题
考察点:动态规划
Description:
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
0 <= nums.length <= 100
0 <= nums[i] <= 400
(1)自己的解法：
动态规划维护一个数组dp,dp[i]表示从开始到第i个房间位置可以偷窃的最大值，更一般的情况，dp[0]=nums[0],dp[1]=max(nums[0],nums[1])，对于后面的问题，当到第i个房间时，可以选择不偷窃，此时的收益就是dp[i-1]，也可以选择偷窃，则此时的收益是dp[i-2]+nums[i]，比较更新最大收益即可，最后返回数组dp的最后一个元素，代码如下：
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l=len(nums)
if l==0:
return 0
if l<=2:
return max(nums)
else:
dp=[0]*(l)
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
for i in range(2,l):
print(i)
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
return dp[l-1]
Problem 3
找数组中的最大子数组乘积
Description:
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
（1）自己的解法：
维护一个局部最优和全局最优的数组，局部最优数组一定包含当前所在下标对应的nums中的元素，这个思路是对的，但对于每次的更新考虑不全，于是参考网上的代码.
def maxProduct(nums):
# [-3, -4, -2, 10]
ans, cur_max, cur_min = -1111, 0, 0
for num in nums:
if num > 0:
cur_max, cur_min = max(num, num * cur_max), min(num, num * cur_min)
print(cur_max,cur_min)
else:
cur_max, cur_min = max(num, num * cur_min), min(num, num * cur_max)
print(cur_max,cur_min)
ans = max(ans, cur_max)
print(ans)
return ans if ans else max(nums)
这里遇到了两个之前写代码没有遇到的坑：
（1）关于代码连写
#这样连着写
cur_max, cur_min = max(num, num * cur_max), min(num, num * cur_min)
#这样分开写
cur_max=max(num, num * cur_max)
cur_min=min(num, num * cur_min)
运行结果竟然不一样
查了下网上的结果，说是合在一起写是并行的，第一个赋值并没有生效
（2）关于数组赋值
a=b=[1,2,3]
b.append(4)
print(a)
这里a只是一个引用，是b的浅拷贝，b改变，a也会跟着改变，若想实现a,b的改变不受影响，需要给a单独开辟一个内存空间，实现深拷贝。
