JSFiddle - React, Tailwind, and code Playground

Return highest sum of array elements divisible by n (By Dynamic Programming).

by Nalin Sajwan

JavaScript

let arr = [3, 6, 5, 1, 8];

let div = 3;

let allSums = [], allMatchesSums = [];

function findAllSum(arr, maxL) {

    var sum = 0;

    for (var i = 0; i < maxL; i++) {
        sum += arr[i];
    }
    
    var dp = (
        function (dims) {
            var allocate = function (dims) {
                if (dims.length == 0) {
                    return false;
                } else {
                    var array = [];
                    for (var i = 0; i < dims[0]; i++) {
                        array.push(allocate(dims.slice(1)));
                    }
                    return array;
                }
            };
            return allocate(dims);
        }
    )(
        [
            maxL + 1,
            sum + 1
        ]
    );

    // Iteration 1 result.
    // console.log("1. dp ==> ", JSON.parse(JSON.stringify(dp)));

    for (var i = 0; i <= maxL; i++) {
        dp[i][0] = true;
    }
    
    // Iteration 2 result.
    // console.log("2. dp ==> ", JSON.parse(JSON.stringify(dp)));

    for (var i = 1; i <= maxL; i++) {

        // console.log("\n1. i ==> ", i)
        // console.log(`arr[${i - 1}] ==> `, arr[i - 1])

        // Setting values of possible sums by index true.
        dp[i][arr[i - 1]] = true;

        // Looping and setting all other possible values.
        for (var j = 1; j <= sum; j++) {

            // console.log("\n2. i ==> ", i, i-1)
            // console.log("j ==> ", j)
            // console.log(`j + arr[${i - 1}] ==> `, j + arr[i - 1])

            if (dp[i - 1][j] === true) {
                // console.log("entered.")
                dp[i][j] = true;
                dp[i][j + arr[i - 1]] = true;
            }
        }
    }
    
    // Iteration 3 result.
    // console.log("3. dp ==> ", JSON.parse(JSON.stringify(dp)));

    for (var j = 0; j <= sum; j++) {
    
        // console.log(`\ndp[${maxL}][${j}] ==> `, dp[maxL][j])

        if (dp[maxL][j] === true) {

            allSums.push(j);

            if (j % div...