- Published on

# number solitair

- Authors
- Name
- Moch Lutfi
- @kaptenupi

## Problem

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

## Solution

_33package main_33_33import (_33 "fmt"_33 "math"_33)_33_33func main() {_33 fmt.Println(Solution([]int{1, -2, -0, 9, -1, -2})) // it should be 8_33}_33_33func Solution(A []int) int {_33 n := len(A)_33 dp := make([]int, n)_33 dp[0] = A[0]_33 for i := 1; i < n; i++ {_33 maxVal := math.MinInt_33 for j := 1; j <= 6; j++ {_33 if i-j >= 0 {_33 maxVal = max(maxVal, dp[i-j]+A[i])_33 }_33 }_33 dp[i] = maxVal_33 }_33 return dp[n-1]_33}_33_33func max(a, b int) int {_33 if a > b {_33 return a_33 }_33 return b_33}

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.