如何从中推导出第一个子序列,使其元素之和相等且元素数相同?

How to derive the first subsequence from such that the sum of their elements is equal and the number of elements is the same?

提问人:vegaLDN 提问时间:11/28/2022 更新时间:11/28/2022 访问量:33

问:

我有一个程序,可以找到一个元素总和最大的子序列,如果有这样的序列(总和相同,但元素数量不同,则打印元素最少的子序列)。但还有一个条件“如果有 2 个或更多序列具有相同数量和相同数量的元素,则从列表开头显示第一个序列”。我显示最后一个。

    import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//4 пп
public class Main {
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(-9999);
    list.add(-9999);
    list.add(100);//4
    list.add(98);//5
    list.add(-5555);
    list.add(99);
    list.add(99);
    list.add(-7866);
    list.add(6);
    list.add(-3);
    list.add(-13434);
    list.add(99);//6
    list.add(90);
    list.add(8);
    list.add(1);//9
    list.add(-9999);
//  list.add(99);//11
//  list.add(99);//12
    list.add(-9999);
    //list.add(198);
    list.add(-444);
    list.add(-7444);
    list.add(100);
    list.add(90);
    list.add(8);
    list.add(-9999);
//  list.add(100);
//  list.add(98);
    list.add(-5555);
    if (list == null || list.size() == 0) {//проверка на пустоту листа
        System.out.println("empty array");
        return;
    }

    int maxSumStartIndex = 0;
    int maxSumLastIndex = 0;
    int maxSum = list.get(0);

    int lastSumStartIndex = 0;
    int lastSum = list.get(0);

    for (int i = 1; i < list.size(); i++) {

        lastSum += list.get(i);
        if (lastSum < list.get(i)) {
            lastSum = list.get(i);
            lastSumStartIndex = i;
        }
        int maxSumLength = i - maxSumStartIndex;

        if (maxSum < lastSum) {
            maxSumStartIndex = lastSumStartIndex;
            maxSumLastIndex = i;
            maxSum = lastSum;
        }
        if (maxSum == lastSum) {
            if (maxSumLastIndex - maxSumStartIndex < i - lastSumStartIndex) continue;//для минимальной длины
            maxSumStartIndex = lastSumStartIndex;//крч надо чтобы тут 11
            maxSumLastIndex = i;// а тут 12
            maxSumLength = maxSumLastIndex - maxSumStartIndex + 1;
        }

    }

    System.out.println("sum( arr[" + maxSumStartIndex + "] .. arr[" + maxSumLastIndex + "] ) = " + maxSum);
    for (int i = maxSumStartIndex; i <= maxSumLastIndex; i++) {
        System.out.print(list.get(i) + " ");
    }
}

}

预期输出: 100 98 (FIRST) 我的输出: 99 99(秒)

Java 列表 算法 序列

评论


答:

0赞 vegaLDN 11/28/2022 #1

添加以下内容,如上一个 IF 语句:

if(list.get(maxSumStartIndex) + list.get(maxSumLastIndex) == maxSum && maxSumStartIndex > 0 && list.get(maxSumStartIndex) != list.get(maxSumLastIndex)){
            maxSumStartIndex = list.indexOf(maxSum - list.get(maxSumStartIndex));
            maxSumLastIndex = list.indexOf(maxSum -  list.get(maxSumLastIndex));
        }