Вернуть максимум из получения левого или правого значения массива

Question

{1,2,3,4,1,2,3,4,1}

Я должен умножить индекс на значение внутри этого.Я могу взять значение только слева или справа от массива.

Например:

Если я возьму ТОЛЬКО число слева, у меня будет 1x1 + 2x2 + 3x3 + 4x4+ 1x5 + 2x6 + 3*7 + 4x8 + 1x9 = 109 points.

Если бы я каждый раз брал число с правого конца, у меня было бы 1x1+4x2+3x3+2x4+1x5+4x6+3x7+2x8+1x9 = 101 points

Если бы я чередовал прием пищи с левого и правого концов (начиная слева), я бы набрал 1x1+1x2+2x3+4x4+3x5+3x6+4x7+2x8+1x9 = 111 points

Однако правильное решение:

1x1+1x2+2x3+3x4+4x5+1x6+2x7+3x8+4x9 = 121 points 

Мой код очень уродлив, но кто-нибудь может мне помочь с этим?

public class CandyRoll {
    static int total = 0;
    static int test (List<Integer> list, int index, int multiplier) {
        //Base Case
        if (list.size() < 1) { return -1;}


        if ((list.get(index) * multiplier) == (list.get(list.size() - 1) * multiplier)){
            total = total + list.get(index) * multiplier;
            multiplier++;
            //list.remove(index);
            index++;
            test(list, index, multiplier);
        } else if ((list.get(index) * multiplier) < (list.get(list.size() - 1) * multiplier)) {
            total = total + list.get(index) * multiplier;
            multiplier++;
            //list.remove(index);
            index++;
            test(list, index, multiplier);
        } else if ((list.get(index) * multiplier) > (list.get(list.size() - 1) * multiplier)) {
            total = total + list.get(list.size() - 1) * multiplier;
            multiplier++;
            //list.remove(list.size() - 1);
            index++;
            test(list, index, multiplier);
        }

        //Given example should be 121.
        return total;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);

        int index = 0;

        System.out.println(test(list, index, 1));
    }

}

Answer 1

Эта проблема становится намного легче, если вы сделаете небольшой умственный сдвиг.Вместо того, чтобы думать об этом как об индексе, умноженном на текущее значение, думайте об этом, как я беру сумму того, что осталось, затем удаляю одно значение.Таким образом, взяв {1,2,3,4,1,2,3,4,1} и взяв числа только слева, вы получите

(1+2+3+4+1+2+3+4+1) +
(  2+3+4+1+2+3+4+1) +
(    3+4+1+2+3+4+1) +
(      4+1+2+3+4+1) +
(        1+2+3+4+1) +
(          2+3+4+1) +
(            3+4+1) +
(              4+1) +
(                1)

И поочередно даст вам:

(1+2+3+4+1+2+3+4+1) +
(  2+3+4+1+2+3+4+1) +
(  2+3+4+1+2+3+4  ) +
(    3+4+1+2+3+4  ) +
(      4+1+2+3    ) +
(      4+1+2      ) +
(        1+2      ) +
(        1        )

Ваше оптимальное решение становится:

 1x1+1x2+2x3+3x4+4x5+1x6+2x7+3x8+4x9

(1+2+3+4+1+2+3+4+1) +
(  2+3+4+1+2+3+4+1) +
(  2+3+4+1+2+3+4  ) +
(    3+4+1+2+3+4  ) +
(      4+1+2+3+4  ) +
(        1+2+3+4  ) +
(          2+3+4  ) +
(            3+4  ) +
(              4  )

И т. Д.

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

Answer 2

Вот рекурсия в JavaScript:

function f(A, l=0, r=A.length-1, memo={}){
  if (memo.hasOwnProperty([l, r]))
    return memo[[l, r]];

  const i = A.length - (r - l);

  if (l == r)
    return memo[[l, r]] = i * A[l];
  
  return memo[[l, r]] = Math.max(
    i * A[l] + f(A, l + 1, r, memo),
    i * A[r] + f(A, l, r - 1, memo)
  );
}

let A = [1,2,3,4,1,2,3,4,1];
console.log(f(A));