В своем первом ответе я рассмотрел проблему ОП в «умножении двух больших чисел».Оказывается, это желание - лишь малая часть гораздо более серьезной проблемы, которую я собираюсь рассмотреть сейчас:
"Я до сих пор не пришел к окончательному скелету моего алгоритма.Интересно, не могли бы вы помочь мне с этим? "
(см. вопрос для описания проблемы)
Все, что я собираюсь сделать, это объяснить подход, предложенный Амноном чуть более подробно, так что вся заслуга должна идти к нему.
Вы должны найти самый большой продукт непрерывного подсписка из списка целых чисел, которые имеют степени 2. Идея состоит в том, чтобы:
- Вычисляет произведение каждого непрерывного подсписка.
- Возвращает самый большой из всех этих продуктов.
Вы можете представитьподсписок по его start и end индексам.Для start=0 существует n-1 возможных значений для end, а именно 0..n-1.При этом создаются все подсписки, которые начинаются с индекса 0. На следующей итерации вы увеличиваете start на 1 и повторяете процесс (на этот раз существует n-2 возможных значений для end).Таким образом, вы генерируете все возможные подсписки.
Теперь для каждого из этих подсписков вы должны вычислить произведение его элементов - то есть придумать метод computeProduct(List wholeList, int startIndex, int endIndex).Вы можете использовать встроенный класс BigInteger (который должен уметь обрабатывать ввод, предоставленный вашим назначением), чтобы избавить вас от дальнейших проблем, или попытаться реализовать более эффективный способ умножения, как описано другими.(Я бы начал с более простого подхода, так как легче увидеть, правильно ли работает Ваш алгоритм, и сначала попытаться его оптимизировать.)
Теперь, когда вы можете перебирать все подсписки и вычислять произведение ихэлементы, определение подсписка с максимальным продуктом должно быть самой простой частью.
Если вам все еще трудно установить связь между двумя шагами, сообщите нам об этом - но, пожалуйста, также предоставьте нам черновик вашегокод, как вы работаете над проблемой, чтобы мы не создавали пошаговое построение решения и не копировали и не вставляли его.
править: Скелет алгоритма
public BigInteger listingSublist(BigInteger[] biArray)
{
int start = 0;
int end = biArray.length-1;
BigInteger maximum;
for (int i = start; i <= end; i++)
{
for (int j = i; j <= end; j++)
{
//insert logic to determine the maximum product.
computeProduct(biArray, i, j);
}
}
return maximum;
}
public BigInteger computeProduct(BigInteger[] wholeList, int startIndex,
int endIndex)
{
//insert logic here to return
//wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
// wholeList[endIndex]);
}