Наименьший подмассив с наибольшей суммой элементов

Вопрос-ответ JavaScript
1

Eсть массив A кандидатов на работу, где элемент позиции i показывает количество навыков кандидата на той же позиции. Нужно в массиве найти тот наименьший подмассив, так чтобы в подмассиве количество навыков превышало количество навыков остальних кандидатов. Компания должен принимать на работу по крайней мере двух кандидатов.

Нужно написать функцию которая получает массив и возвращает наименьшую подмассив сумма элементов которого превышают сумму остальних эелементов (исходного массива).

function smallSubArray(arr) { }

console.log(smallSubArray([4, 2, 8, 1, 0, 0, 5]));        // [8, 5]
console.log(smallSubArray([9, 1, 5, 2, 3, 0, 0, 0, 0]));  // [9, 5]
console.log(smallSubArray([2, 2, 2, 0, 0, 0, 0]));        // [2, 2]  
console.log(smallSubArray([10, 9, 9, 9, 9, 2, 1]));       // [10, 9, 9]

Поможете решить задачу?

2

подумаем логично,

  1. сума всех элементов
  2. отсортировать элементы.
  3. суммировать элементы начиная с самого большого, пока сумма не станет больше чем половина суммы всего массива. Это и будут нужные элементы.

Хотя явно есть какая-то мудреная формула для этого.
Вот вам “маленькое” усложнение задачи.

  • Подмножества могут состоять только из смежных элементов
    Следующей лвл усложнения:
  • Элементы должны быть не только смежными, но и схожими. За параметр схожести берется отклонение от среднеарифметического всего подмножества
    Следующей лвл усложнения:
  • Подмножество допускает аномальное отклонение нескольких элементов от среднеарифметического, если длина аномального отрезка не превышает указанное количество элементов. При этом, для вычисления среднеарифметического всего подмножества, используют среднеарифметическое от соседних точек. Не забудьте что аномальный отрезок может быть 2 точки и больше.

Если человек мне решит такое на собеседовании, возьму его вообще невзирая на остальные умения.

3

В чем вопрос? Как составить алгоритм действий?

4

Здраствуйте Дмитрий я пробовал написать так но наверное подход неверный

function smallSubArray(arr) {

    let subArr = []

    l = arr.length;

    var max = arr[0];

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

        if (max < arr[i]) {

          max = arr[i];

        }

    }

    for (var i = 0; i < l; i++) { 

        if (max != arr[i]) {

          var max1 = arr[i];

          break;

        }

    }

    for (var i = 0; i < l; i++) {

        if (max1 < arr[i] && arr[i] != max) {

          max1 = arr[i];

        }

    }

    subArr.push(max, max1)

    return subArr;

}
    console.log(smallSubArray([4, 2, 8, 1, 0, 0, 5]));        // [8, 5]
    console.log(smallSubArray([9, 1, 5, 2, 3, 0, 0, 0, 0]));  // [9, 5]
    console.log(smallSubArray([2, 2, 2, 0, 0, 0, 0]));        // [2, 2]  
    console.log(smallSubArray([10, 9, 9, 9, 9, 2, 1]));       // [10, 9, 9]

В последних двух случиях код правильно не работает
Поможете написать верный алгоритм?

5
  1. Давай сразу на “ты”.
  2. Прикладывай не только код но и описание словами своей стратегии.
6

Большое спасибо за советы

7

Ладно дорогой Дмитрий.
Я просто старался найти первый и второй максимальные элементы и добавил в новый пустой массив

8

Это проще и вернее делать через сортировку + slice первых двух элементов в отсортированном массиве.

9

К сожелению через slice у меня не получился но пробовал так
function smallSubArray(arr) {

    let sum = 0;

    let sum1 = 0;

    let arr1 = arr.sort((a, b) => b - a)

    let arr3 = []

    for (let i = 0; i < arr.length; i++) {

        sum += arr[i];

    }

    for (let i = 0; i < arr1.length; i++) {

        sum1 = arr1[i] + arr[i + 1] + arr[i + 2];

        if (sum1 > sum - (arr[i] + arr[i + 1])) {

            arr3.push(arr1[i], arr1[i + 1])

            break

        }

    }

    return arr3;

}

console.log(smallSubArray([4, 2, 8, 1, 0, 0, 5]));

console.log(smallSubArray([2, 2, 2, 0, 0, 0]));

console.log(smallSubArray([9, 5, 1, 2, 3, 0, 0, 0]));

console.log(smallSubArray([10, 9, 9, 9, 9, 2, 1]));

и опять в последнем случае функция неверно работает должен выводиться [10,9,9]

10

Верно. Не работает потому что тебе нужно не фиксированно брать 2 первых элемента массива, а постепенно наращивать массив пока сумма элементов не станет больше суммы остального массива.

Ты выше писал что берешь только 2 первых элемента. Но это не подходящая стратегия. Нужно пересмотреть подход.

11

Если можно немного поможешь как написать эту часть алгоритма?

12
  1. Сортируешь массив.
  2. Берешь подмассив с 0 по n, берешь остаток массива (с n по length). Сравниваешь суммы в обоих. На первом шаге n = 1.
  3. Если сумма элементов подмассива больше суммы элементов остатка массива, значит подмассив и есть результат. Если меньше - переходи на шаг 2, и бери подмассив на 1 элемент больше (соответственно остаток массива на 1 меньше).

Тут есть что оптимизировать. “Влоб” понятное и прямолинейное решение выглядит так:

13

Большое спасибо Дмитрий конечно извините но в случае console.log(smallSubArray([10,10,10,3,50])) [50] но должен выводить [50, 10]

14

50 больше чем 33 (сумма остальных элементов). Или ты имеешь в виду что минимальная длина подмассива должна быть 2?

15

Минимальная длина массива должен быть 2

16

Отлично. Мое решение можно поправить так чтобы оно удовлетворяло этому ограничению. Посмотри описание алгоритма. Можем обсудить что в алгоритме нужно поменять. А потом глянь что нужно поменять в коде. Тоже можем обсудить.

17

Получился Дмитрий (i = 1 поменял на i = 2) большое спасибо за твои советы и за то что нашел время и написал алгоритм. Я у тебя многому научился.Большое спасибо…

18

Мне приятно. Для того и поддерживаю этот ресурс.

1 лайк