Блог

Постановка задачи такова: задан целочисленный массив A размера N.

Вы можете выбрать B элементов с левого или правого конца массива A, чтобы получить максимальную сумму. Найдите и верните эту максимально возможную сумму.

ПРИМЕЧАНИЕ: Предположим, что B = 4 и массив A содержит 10 элементов, тогда:

Вы можете выбрать первые четыре элемента или можете выбрать последние четыре элемента или можете выбрать 1 спереди и 3 сзади и т.д. вам нужно вернуть максимально возможную сумму элементов, которые вы можете выбрать.

 public class Solution {
ArrayList<Integer> c = new ArrayList<>();
ArrayList<Integer> A= new ArrayList<>();
public int solve(ArrayList<Integer> A, int B) {
   
    if (B>A.size()){
        int sum=0;
        for(int i=0;i<A.size();i  )
         sum= sum A.get(i);
        return sum;
    }

   int max_sum=0;
 for(int i=0;i<A.size();i  ){
  if((max_sum<suffix(A.size()-(B-i)) prefix(i-1)) ){
       max_sum=suffix(A.size()-(B-i)) prefix(i-1);
     }
    }
    return max_sum;
}
    
    int prefix_sum=0;
  int prefix(int a)   {
      
       for(int p=0;p<a 1;p  ){
           c=A;
            prefix_sum=prefix_sum   c.get(p);
            }
          return prefix_sum;
                     }

           int suffix_sum=0;
           int suffix(int b){
               c=A;
        for(int q=b;q<c.size();q  ){
           suffix_sum=suffix_sum c.get(q);
          }
            return suffix_sum;
         }
  

}

Я получаю ошибку времени выполнения, я попытался реализовать методы suffix и prefix, которые возвращают сумму из индекса [0, i] и sum из [i, N-i] соответственно, затем в функции solve я пытаюсь найти сумму префикса [a-1] суффикс [N-(b-a)] и узнать максимальную сумму, синтаксис полностью правильный, что-то не так с логикой, которую я предполагаю, пожалуйста, помогите мне найти правильное решение, исправив этот код вместо предоставления альтернативного метода

     package com.array;

    import java.util.Arrays;
    import java.util.List;

    public class PickFromBothSides {

        public static void main(String[] args) {
            Integer[] arr = { 5, -2, 3, 1, 2 };
            System.out.println(solve(Arrays.asList(arr), 3));

        }

        public static int solve(List<Integer> A, int B) {

            int n = A.size();

            int result = 0;

            for (int i = 0; i < B; i  ) {
                result  = A.get(i);
            }

            int sum = resu<

            for (int i = 0; i < B; i  ) {
                sum -= A.get(B - 1 - i);
                sum  = A.get(n - 1 - i);

                result = Math.max(result, sum);
            }

            return resu<

        }
    }
  

Время выполнения O (n)
Сложность пространства O (1)

Вы объявляете int prefix_sum=0; и int suffix_sum=0; как поля, а не как локальные переменные соответствующих методов.

Вы вызываете suffix(A.size()-(B-i)) so в своем примере, который есть 10 - (4 -i) который есть 6 i . Вы выполняете итерацию, i находясь в диапазоне {0, …, 10}, поэтому значением 6 i будут все числа с 6 по 16. Вы не можете выполнить индексацию в массиве выше 9, поэтому вы получаете исключение.

Вам нужно изменить

 for(int i=0;i<A.size();i  ){
  

Для

 for(int i=0; i <= B; i  ){
  

потому что вы пытаетесь спрашивать каждую итерацию «сколько чисел берется с начала»? 0, 1, 2, 3 или 4, если B равно 4

Другие обновления:

1. Вы вызываете suffix(A.size()-(B-i)) prefix(i-1)) два раза подряд. Вызовите это только один раз, сохраните в переменной и повторно используйте.

2. Вы вызываете prefix(i-1) , но внутри prefix() вы используете параметр a как a 1 . Вам не нужно вычитать единицу и добавлять ее к одному и тому же