Python O(n) time and space, using DP


#1
class Solution:
    # @param A : list of list of integers
    # @return an integer
    def adjacent(self, A):
        m = 2
        n = len(A[0])
        if n==1:
            return(max(A[0][0],A[1][0]))
    
        dp = [[0 for i in range(n)] for i in range(m)]
        dp[0][-1]=A[0][-1]
        dp[1][-1]=A[1][-1]
    
        dp[0][-2]=max(A[0][-2],A[0][-1])
        dp[1][-2]=max(A[1][-2],A[1][-1])
    
        for i in range(n-3,-1,-1):
            dp[0][i] = max(dp[0][i+1], A[0][i]+max(dp[0][i+2],dp[1][i+2]))
            dp[1][i] = max(dp[1][i+1], A[1][i]+max(dp[0][i+2],dp[1][i+2]))
        
        return(max(dp[0][0],dp[1][0]))

#2

I too initially solved using a 2xN dp array but we can solve with 1xN array.

class Solution:
    # @param A : list of list of integers
    # @return an integer
    def adjacent(self, A):

        if len(A[0]) == 1:
            return max(A[0][0], A[1][0])

        n = len(A[0])

        mem = [0]*n

        for j in range(n):
            if j == 0:
                mem[j] = max(A[0][j], A[1][j])
            elif j == 1:
                mem[j] = max(A[0][j], A[1][j], mem[j-1])
            else:
                mem[j] = max(mem[j-1], max(A[0][j], A[1][j]) + mem[j-2])

        return mem[-1]

Also if anyone is looking for python solution the fastest solution is interesting