不相邻最大子序列和

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算
# @param n int整型 数组的长度
# @param array int整型一维数组 长度为n的数组
# @return long长整型
# 打家劫舍
class Solution:
    def subsequence(self , n , array ):
        # write code here
        if not n:
            return 0
        if n <= 2:
            return max(max(array), 0)
        dp = []
        dp.append(max(array[0], 0))
        dp.append(max(max(array[:2]), 0))
        for i in range(2, len(array)):
            dp.append(max(dp[i-1], dp[i-2]+array[i]))
        return dp[-1]
    

class Solution:
    def subsequence(self , n , array ):
        su, s = [ 0 ] * n, [ 0 ] * n
        if array[0] > 0: s[0] = array[0]
        ans = max(0, s[0])
        for i in range(1, n):
          su[i] = max(su[i-1], s[i-1])
          s[i] = max(su[i-1], su[i-1] + array[i])
          ans = max(ans, su[i], s[i])
        return ans