# number solitair

1 min read Tweet this post
Section titled Problem

## Problem

https://app.codility.com/programmers/lessons/17-dynamic_programming/number_solitaire/

Section titled Solution

## Solution

``````package main

import (
"fmt"
"math"
)

func main() {
fmt.Println(Solution([]int{1, -2, -0, 9, -1, -2})) // it should be 8
}

func Solution(A []int) int {
n := len(A)
dp := make([]int, n)
dp[0] = A[0]
for i := 1; i < n; i++ {
maxVal := math.MinInt
for j := 1; j <= 6; j++ {
if i-j >= 0 {
maxVal = max(maxVal, dp[i-j]+A[i])
}
}
dp[i] = maxVal
}
return dp[n-1]
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

``````

The code above implements a dynamic programming algorithm to find the maximum sum of an array `A` of integers. The array `A` represents a sequence of numbers, and the goal is to find the maximum sum of a sub-sequence of `A` with the restriction that the sub-sequence can only have a maximum length of 6.

The algorithm starts by initializing an array `dp` with the same length as `A`. The first element of `dp` is set to the first element of `A`, which is `A[0]`.

Next, the code loops through each element of `A` starting from index 1 to the end of the array `A`. For each element, the code calculates the maximum value that can be achieved by adding the current element to the sum of one of the previous 6 elements. It does this by looping through the previous 6 elements and checking if the current index minus `j` (where `j` is the loop variable) is greater than or equal to zero. If this is the case, the maximum value is updated by taking the maximum of the current `maxVal` and the sum of the current element of `A` and the corresponding element in `dp` (which represents the maximum sum of a sub-sequence ending at that element).

The calculated maximum value is then stored in the current element of `dp`. This process continues until the end of the loop, after which the last element of `dp` is returned, which represents the maximum sum of a sub-sequence of `A` with the restriction that the sub-sequence can only have a maximum length of 6.

The `max` function is a helper function that returns the maximum of two integers.

programming go dynamic-programming snippets cp