Поиск максимальных элементов (последовательных), сумма которых меньше заданного значения?

Итак, у меня есть массив всех положительных натуральных чисел. Мне дано пороговое значение. Я должен выяснить, максимальное количество чисел (последовательных), сумма которых меньше заданного порогового значения.Поиск максимальных элементов (последовательных), сумма которых меньше заданного значения?

For example, 
IP: arr = {3,1,2,1} 
Threshold = 5 

O/P: 3

Максимальный размер входного массива может быть 10^5.

В принципе, я думал об алгоритме, который вычисляет количество элементов в подмножествах исходного массива, сумма которых будет меньше заданного порога. Но это приведет к сложности O (N^2). Может ли кто-нибудь предложить лучший алгоритм? Я не ищу код, и только алгоритм/псевдокод будет отлично. Благодаря!

источник

2015-06-15 John Lui

Попробуй ниже ...

public int maximumElem(int[] array,int threshold) 
{ 
    int sum = 0; 
    for(int i=0;i<array.length;i++) 
    { 
    sum = sum + array[i]; //sum the values at each index 
    if(sum >= threshold) //check condition 
     return (i+1); // if sum is reaching the threshold then return the index 
    } 
}

Надеется, что это помогает ...

Пожалуйста, дай мне знать, если у вас есть какие-либо дополнительные вопросы ...

источник

2015-06-15 08:53:58

Но он не вернет максимальный счет. Например, если входной массив был бы «6 1 2 3» и «threshold = 5», ваш код вернет «1», когда он вернет «2». –

для 6 1 2 3 и пороговое значение 5, максимальное число равно 6? ...как бы это было 7 –

Это будет бит, но должен указывать на решение O (n)

Пройдите по списку с двумя указателями, начиная с самого начала, мы будем называть один из них, а другой - тропой, так как один ведет и одна тропа.

отслеживать сумму от тропы до свинца; и длину в настоящее время встречающейся самой длинной действующей последовательности.

Пока текущая сумма меньше (или равна) порогового значения, продвиньте указатель поворота и скорректируйте сумму, добавив значение, на которое оно теперь указывает. Если сумма по-прежнему меньше (или равна) порогового значения, то последовательность от тропы до свинца является возможной.

Пока текущая сумма больше порога, продвигайте указатель траектории.

Продолжить, пока ведущий указатель не достигнет конца.

Вам нужно будет заполнить детали и выполнить их тщательно, но для меня это кажется достаточно хорошим.

источник

2015-06-15 08:56:30 moreON

Я реализовал то, что вы сказали, и я отредактировал свое оригинальное сообщение, чтобы включить код. Однако в случае, если порог чрезвычайно велик (8 цифр), а число элементов в массиве равно '100000', то оно все равно дает превышение лимита времени. Можете ли вы рассказать мне, как я могу оптимизировать свой код дальше? –

Не повторяйте расчет суммы. Воспользуемся тем, что сумма от Ai до Aj равна сумме от Ai до Aj-1 + A [j] – moreON

Я хотел бы попробовать следовать:

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

источник

2015-06-15 08:56:46 MaMazav

Это звучит точно так же, как мое решение, которое мы разместили в почти одинаковые времена. Это дает мне больше уверенности в них. – moreON

public static int maximumSum(int[] array, int t){ 
    int maxSum = 0; 
    int curSum = 0; 
    int start = 0; 
    int end = 0; 
    while(start < array.length){ 

     if(curSum > maxSum && curSum <= t){ 
      maxSum = curSum; 
     } 
     if(curSum <= t && end < array.length){ 
      curSum += array[end]; 
      end += 1; 

     } 
     else{ 
      curSum -= array[start]; 
      start+= 1; 
     } 
    } 
    return maxSum; 
}

Сложность этого кода представляет собой О (2 * N), который, по существу, О (п). Я не могу придумать никаких улучшений.

источник

2016-11-03 20:14:50

Поиск максимальных элементов (последовательных), сумма которых меньше заданного значения?

ответ

Смежные вопросы