两边都选？

bjp0bcyl 于 2021-07-06 发布在 Java

关注(0)|答案(2)|浏览(297)

问题陈述是：给定一个大小为n的整数数组。
您可以从数组a的左端或右端选取b个元素，以获得最大和。找到并返回这个最大可能的总和。
注：假设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;
         }

}
我得到了运行时错误，我尝试实现了后缀和前缀方法，分别返回索引[0，i]和[i，n-i]的和，然后在solve函数中我尝试找到前缀[a-1]+后缀[n-（b-a）]的和，并找出最大和，语法完全正确，我假设的逻辑有问题，请通过更正此代码而不是提供替代方法来帮助我找到正确的解决方案

Java Arrays ArrayList dynamic-programming

来源：https://stackoverflow.com/questions/63537467/pick-from-both-sides

2条答案

按热度按时间

igsr9ssn1#

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 = result;

            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 result;

        }
    }

运行时o（n）空间复杂度o（1）

赞(0）回复(0）举报 2021-07-06

ftf50wuq2#

你在宣布 int prefix_sum=0; 以及 int suffix_sum=0; 作为字段，而不是作为各自方法的局部变量。
你在打电话吗 suffix(A.size()-(B-i)) 你的例子就是 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++){

因为您试图询问每个迭代“从一开始取了多少个数字”？如果b为4，则为0、1、2、3或4
其他升级：
你在打电话吗 suffix(A.size()-(B-i))+prefix(i-1)) 连续两次。只调用一次，将其存储在变量中并重用。
你在打电话吗 prefix(i-1) 但在prefix（）中，您使用的是参数 a 作为 a + 1 . 你不需要在同一件事上减去一，再加上一

赞(0）回复(0）举报 2021-07-06

我来回答

两边都选？

2条答案

相关问题

热门标签

最新问答