How to Solve Maximum Sum of a Subsequence Problem

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Input: [3, 2, 7, 10]
Output: [3 10] 13

Input: [3, 2, 5, 10, 7]
Output: [3 5 7] 15

Input: [3, 20, 5, 10, 7]
Output: [20 10] 30

Input: [3, 10, 30, 100, 40]
Output: [10 100] 110

Input: [3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50]
Output: [10 2 30 40 50] 132

This solution is not an optimal solution.

package main

import (
    "fmt"
)

func sum(a []int) int {
    s := 0
    for _, v := range a {
        s += v
    }
    return s
}

func maxSumSubsequence(a []int) []int {
    result := [][]int{}
    // odd
    recurseMaxSumSub(a, 0, []int{}, &result)
    // even
    recurseMaxSumSub(a, 1, []int{}, &result)
    max := 0
    var maxSubsequence []int
    for _, v := range result {
        s := sum(v)
        if max == 0 {
            max = s
            maxSubsequence = v
        } else if max < s {
            max = s
            maxSubsequence = v
        }
    }
    return maxSubsequence
}

func recurseMaxSumSub(a []int, idx int, accu []int, result *[][]int) {
    if idx < len(a) {
        recurseMaxSumSub(a, idx+2, append(accu, a[idx]), result)
    } else {
        *result = append(*result, accu)
    }

    if idx+1 < len(a) {
        recurseMaxSumSub(a, idx+3, append(accu, a[idx+1]), result)
    } else {
        *result = append(*result, accu)
    }
}

func main() {
    out := maxSumSubsequence([]int{3, 2, 7, 10})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 2, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 20, 5, 10, 7})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 30, 100, 40})
    fmt.Println(out, sum(out))
    out = maxSumSubsequence([]int{3, 10, 1, 2, 3, 30, 4, 40, 5, 6, 50})
    fmt.Println(out, sum(out))
}