In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/17-dynamic_programming/number_solitaire/
- Time Complexity:
Solution:
Solution to Codility's Number Solitaire problem which is from the Codility Lesson 17: Dynamic programming and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to in a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6. You can find the question of this NumberSolitaire problem in the Codility website.
package Codility.Lesson17;
import java.util.*;
public class NumberSolitaire {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a1 = { 1, -2, 0, 9, -1, -2 };
int result = solution(a1);
System.out.println(result);
}
public static int solution(int[] A) {
int[] dp = new int[A.length];
dp[0] = A[0];
// build up from "dp[1], dp[2], ..., dp[A.length-1]"
for (int i = 1; i < A.length; i++) {
// keep the biggest one
// be very careful: could be negtive (so use Integer.MIN_VALUE)
int max = Integer.MIN_VALUE;
// a die could be "1 to 6"
for (int die = 1; die <= 6; die++) {
if (i - die >= 0) {
// very important: not "A[i-die]+A[i]"
// instead, have to use "dp[i-die]+A[i]"
max = Math.max(dp[i - die] + A[i], max);
}
}
dp[i] = max; // keep the best one as the dp value
}
return dp[A.length - 1];
}
}