Problem
https://app.codility.com/programmers/lessons/17-dynamic_programming/number_solitaire/
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.