'''
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

例子
maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) -> 6
假设
输入的数组元素为整数
tips
枚举所有子数组，检查每个子数组和
你能想到更优的解法吗？(利用动态规划思想)

动态规划问题，具体解法都是通过一个二维数组来存储中间环节的最优解，然后求二维数组的最大值或者最后一个值。
还有一种情况，如果当前状态只跟前面的一个状态有关，那么二维数组是可以优化为一维数组，这样空间负责度从O(n**2) 优化到 O(n)
'''

设立个一维数组，记录当前下标处的最大子序列

状态转移方程：当前值，或者当前值加上上一个最优值

def maxSubArray(nums):
l = len(nums)
res = [0 for i in range(l)]
print(res)
# 对数列遍历，如果前面子序列的和小于0， 那么就不用费力计算了，重新开始统计，子序列开始就是本身
# 如果前面子序列的和大于0， 那么可以加上本身，继续舞
for i in range(l):
if i == 0:
res[0] = nums[0]
else:
if res[i-1] <= 0:
res[i] = nums[i]
else:
res[i] = nums[i] + res[i-1]
print(res)
return max(res)

s1 = [-2,1,-3,4,-1,2,1,-5,4]

s2 = ''

print(maxSubArray(s1))

'''
百度了解下更多的动态规划问题
2.2 最长公共子串
题目描述：a b两个字符串，求a b的最长公共子串。子串与子序列不同，子串必须是连续的，而子序列可以不连续。例如：

输入: a="abccbca"，b="bccca"
输出: 3
解释: 最长公共子序列就是"bcc"，为3

状态转移方程:

'''
a = 'abccbca'
b = 'bccca'

def findCommonSubStr(a, b):
la = len(a)
lb = len(b)
# 这里的矩阵为何要比长度多一个单位?
res = [[0 for i in range(lb+1)] for j in range(la+1)]
print(res)
mmax = 0
for i in range(1, la+1):
for j in range(1, lb+1):
if a[i-1] == b[j-1]: #为什么只有当a[i-1]==b[j-1]时候才会+1 , i,j都是从1开始的，所以i-1,j-1就是当前元素，当前相等了，用res[i][j]表示当前的最大长度
res[i][j] = res[i-1][j-1] + 1
print(res)
mmax = max(res[i][j], mmax)
return (mmax)

print(findCommonSubStr(a, b))

'''
最长子序列
2.3 最长公共子序列（Leetcode1143）
题目描述：a b两个字符串，求a b的最长公共子序列。这里与上一题要区分开，重点是子序列可以是不连续的。

输入: a="abccbca"，b="bccca"
输出: 6
解释: 最长公共子序列就是"bccca"，为6
'''

动态规划 如果相等就加1 ，不相等就取出(a字符串少一个字符，b字符串少一个字符)

def findSubSequence(a, b):
la = len(a)
lb = len(b)
res = [[0 for i in range(lb+1)] for j in range(la+1)]
for i in range(1, la+1):
for j in range(1, lb+1):
if a[i-1] == b[j-1]:
res[i][j] = res[i-1][j-1] + 1
else:
res[i][j] = max(res[i-1][j], res[i][j-1])
print(res)
return res[-1][-1]

print(findSubSequence(a, b))

'''
2.5 最长上升子序列（Leetcode300）
题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。例如：

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
'''

动态规划

res[i] 表示以此项为结尾的 最大上升子序列的长度

如果，当前num[i] 比前一项大，那么就可以再前一项res[j]的基础上加1,

def lengthOfLIS(nums):
l = len(nums)
if l == 0:
return 0
res = [1 for i in range(l)] #初始每个位置的最长子序列长度都是1
for i in range(l): #确定到i的最长子序列
max_ = 1
tmp = 0
for j in range(i):
if nums[i] > nums[j]:
tmp = res[j] + 1
# if tmp > max_:
max_ = max(tmp, max_)
res[i] = max_
return res
# pass

nums = [10,9,2,5,3,7,101,1]

print(lengthOfLIS(nums))

'''
2.6 摆动序列（Leetcode376）
题目描述：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。例如：

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
'''
test = [7,4,3,2,1,17,5,10,13,15,10,5,16,8]
def swing(s1):
l = len(s1)
if 0 < l <= 2:
return l
res = [1 for i in range(l)]
# res[i] 是从0到i的最长摆动序列个数
# up = 1
# down = 1#False
for i in range(1, l):
_max = 1
up = 1
down = 1
for j in range(1, i+1):
if s1[j] > s1[j-1]:
up = down + 1
# down = False
elif s1[j] < s1[j-1]:
# up = False
down = up + 1
_max = max(up, down)
res[i] = _max
print(res)
return max(res)
# pass

print(swing(test))

'''
.7 最小路径和（Leetcode64）
题目描述：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。注意：每次只能向下或者向右移动一步。
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
这个题很常见，面试经常被问到。
'''

m = [
[1,3,1],
[1,5,1],
[4,2,1]
]

def minPathSum(grid):
row = len(grid[0])
col = len(grid)
res = [[0 for j in range(col)] for i in range(row)]
print(res)
for i in range(row):
for j in range(col):
if i == 0 and j == 0:
res[i][j] = grid[0][0]
#如果 i=0 第一行只能横着走 ，第一列只能竖着走
if i == 0: #横着只能左边走过
res[i][j] = res[i][j-1] + grid[i][j]
elif j == 0: # 竖着只能上面走下来
res[i][j] = grid[i][j] + res[i-1][j]
else: #否则是向下和向右的最小值
res[i][j] = min(res[i][j-1], res[i-1][j]) + grid[i][j]

print(res)
return res[-1][-1]

print(minPathSum(m))

'''
2.1 经典01背包问题
题目描述：一个人去偷东西，他的背包容量最大为20kg，然后有重量、价值不等的物品，比如重量为2、价值为3的物品，每件物品只能拿一件，求小偷能偷到的物品最大的价值。

"""
物品重量与价值对应关系：
w v
2 3
3 4
5 8
9 10
背包容量：20

test_pack = [[2, 3],
[3, 4],
[4, 5],
[5, 8],
[9, 10]]
'''
def packIssue(pack, n):
l = len(pack)
# 初始化全部为0
#
res = [[0 for i in range(n+1)] for j in range(l+1)]
print(res)
# i 代表物品序列号
for i in range(1, l+1):
# j代表包中剩余容量 对物品i，当剩余容量为j是，最大价值是res[i][j]
for j in range(1, n+1):
# 容量不足
if j < pack[i-1][0]:
res[i][j] = res[i-1][j]
else:
# 占用空间
w = pack[i-1][0]
# 放入当前物品的总价值 占用w，剩余j-w, 当前物品i在j-w剩余空间的最大价值res[i][j-w]
a = res[i-1][j-w] + pack[i-1][1]
# b表示不放入当前物品的总价值
b = res[i-1][j]
# 当前总价值最大
res[i][j] = max(a, b)

print(res)
# print(res[-1][-1])
return res[-1][-1]

test_pack = [[2, 3],
[3, 4],
[4, 5],
[5, 8],
[9, 10]]
print(packIssue(test_pack, 20))