Самый большой продукт в серии (Java)

Question

Я пытаюсь найти 3 соседних числа, которые дают максимальный продукт с учетом 9-значного числа.Например, для числа 198348756 мое решение должно вернуть [8,7,5], так как произведение этого продукта равно 280 и является максимально возможным продуктом. Мой код находит максимальный продукт, но не может вернуть массив цифр, которые создают максимальный продукт.Вместо этого он возвращает последний массив, который проверяет в цикле for.Я не могу понять, почему массив цифр, которые создают максимальный продукт, не хранится в переменной result?

  public class Solution {
  ArrayList<Integer> digits = new ArrayList<>();


  /// digits to int array
  void tocharArray(String num) {
    char[] charArray = num.toCharArray();

    for (Character c : charArray) {
      digits.add(Character.getNumericValue(c));
    }
    //System.out.println(digits);
    //System.out.println(digits.size());
  }


  //gets product of array ex [1,2,3] ->6
  int arrayproduct(ArrayList<Integer> array) {
    int product = 1;
    for(int i=0;i < array.size(); i++) {
      product = product * array.get(i);
    }
    return product;
  }


  ArrayList<Integer> func() {
    ArrayList<Integer> three = new ArrayList<>();
    ArrayList<Integer> result = new ArrayList<>();


    // array of the first 3 digits of the number
    for(int index = 0; index < 3;index++) {
      three.add(digits.get(index));
    }

    //initially the max product is the first 3 digits 
    int maxproduct = arrayproduct(three); 
    System.out.println(three); //from test [1,9,8]
    System.out.println(maxproduct);// from test 72

    ArrayList<Integer> copy = three;

    for(int j = 3 ; j < digits.size();j++) {

      copy.remove(0);
      copy.add(digits.get(j));
      int next = arrayproduct(copy);
      System.out.println(copy);

      if(next > maxproduct) {
        maxproduct = next;
        result = copy;
      }
    }
    System.out.println(maxproduct); // returns 280 which is correct 
    System.out.println(result); // returns [7,5,6]

    return result;

  }

  public static void main(String[] args) {
    String test1 = "198348756";

    Solution sol = new Solution();
    sol.tocharArray(test1); \\[1,9,8,3,4,8,7,5,6]
    sol.arrayproduct(sol.digits); \\returns [7,5,6] which is incorrect
    sol.func();
  }
}

Answer 1

Более легкий подход

ArrayList<Integer> getMaxConsecutive(ArrayList<Integer> arr)
{
    ArrayList<Integer> result = new ArrayList<Integer>();

    int start=-1;
    int max=INT_MIN;
    for(int i=0;i<(arr.size()-3);i++)
    {
         int sum = arr.get(i)+arr.get(i+1)+arr.get(i+2);
         if(sum>max){
             max=sum;
             start = i;
         }
    }

    result.add(arr.get(start));
    result.add(arr.get(start+1));
    result.add(arr.get(start+2));

    return result;
}

Answer 2

Из исходного кода:

for (int j = 3; j < digits.size(); j++) {

    copy.remove(0);
    copy.add(digits.get(j));
    int next = arrayproduct(copy);
    System.out.println("-->" + next);
    System.out.println("-->" + copy);

    if (next > maxproduct) {
        maxproduct = next;
        result = copy;
        System.out.println("result-->" + result);
    }
}

Переменная copy и result являются ссылками на объекты, такими как указатель на C. Таким образом, вам нужно явно копировать (клонировать) все содержимое копии в результирующий объект каждый раз, когда изменяется значение maxproduct. Есть несколько способов достичь этого метода.

Использование метода клонирования - один простой способ сделать это;

result = copy;

до

result = (ArrayList<Integer>)copy.clone();

Итак, метод func выглядит следующим образом:

@SuppressWarnings("unchecked")
ArrayList<Integer> func() {
    ArrayList<Integer> three = new ArrayList<>();
    ArrayList<Integer> result = new ArrayList<>();

    // array of the first 3 digits of the number
    for (int index = 0; index < 3; index++) {
        three.add(digits.get(index));
    }

    // initially the max product is the first 3 digits
    int maxproduct = arrayproduct(three);
    System.out.println(three); // from test [1,9,8]
    System.out.println(maxproduct);// from test 72

    ArrayList<Integer> copy = three;

    for (int j = 3; j < digits.size(); j++) {

        copy.remove(0);
        copy.add(digits.get(j));
        int next = arrayproduct(copy);
        System.out.println(copy);

        if (next > maxproduct) {
            maxproduct = next;
            result = (ArrayList<Integer>)copy.clone();
        }
    }
    System.out.println(maxproduct); // returns 280 which is correct
    System.out.println(result); // returns [7,5,6]

    return result;

}

Тогда выходное сообщение может быть тем, что вы ожидали.

[1, 9, 8]
72
[9, 8, 3]
[8, 3, 4]
[3, 4, 8]
[4, 8, 7]
[8, 7, 5]
[7, 5, 6]
280
[8, 7, 5]

Хорошего кодирования ...

Answer 3

Проблема в этой строке:

ArrayList<Integer> copy = three;

Ваш код предполагает, что copy - это, в общем-то, копия, но на самом деле это псевдоним для того же списка three.

Вы можете исправить это, скопировав список:

ArrayList<Integer> copy = new ArrayList<>(three);

То же самое относится к result = copy - оно должно быть result = new ArrayList<>(copy)

Примечание: Вы можете еще больше упростить этот код, изменив arrayproduct, чтобы взять начальный индекс и длину. Таким образом, вы сможете избежать создания новых списков по ходу дела. Как только будет найдено правильное местоположение, вы сможете сделать копию трехэлементного поддиапазона, позвонив по номеру subList.