在给定的ArrayList中查找具有最大和的子数组

Question

问题描述：

给定CCD_ 2的一个CCD_。查找ArrayList内任何潜在子阵列的最大和的子阵列。

子数组A是连续数字的组合。

子阵列可以是任何长度的n，其中n >= 0。

示例

输入：

[-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18]

解决方案

[17, 0, 0, 9, 20, 0, 7]

这是我迄今为止掌握的代码。

public class MaxSubArray {
public ArrayList<Integer> solution(ArrayList<Integer> nums) {
int maxSubArrSum = Integer.MIN_VALUE;
int greatest = Integer.MAX_VALUE;
int smallest = 0;
int start;
int end;
ArrayList<Integer> maxSubArr;
ArrayList<ArrayList<Integer>> lists = new ArrayList();
try {
for (int left = 0; left < nums.size(); left++) {
int runningSum = 0;
for (int right = left; right < nums.size(); right++) {
runningSum += nums.get(right);
if (runningSum >= maxSubArrSum) {
ArrayList<Integer> temp = new ArrayList<>();
maxSubArrSum = runningSum;
start = left;
end = right;
for (int i = start; i <= end; i++) {
temp.add(nums.get(i));
}
lists.add(temp);
}
}
}
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i).size() < greatest) {
greatest = lists.get(i).size();
smallest = i;
}
}
maxSubArr = lists.get(smallest);
return maxSubArr;
} catch (Exception e) {
e.printStackTrace();
return nums;
}
}
}

我试图迭代numsArrayList，并计算出子阵列的第一个和最后一个大和，并将它们放入ArrayLists的列表中。

在那之后，我试图找出子阵列中哪个的大小最小，并返回它

我在这里做错了什么？

Answer 1

这里有一个更简洁的解决方案

private List<Integer> solution(List<Integer> nums) {
int biggestSumSoFar = Integer.MIN_VALUE;
List<Integer> biggestSubListSoFar = new ArrayList<>();
for (int left = 0; left < nums.size(); ++left) {
for (int right = left + 1; right < nums.size(); ++right) {
List<Integer> currentSubList = subListSum(nums, left, right);
int currentSum = sum(currentSubList);
if (currentSum > biggestSumSoFar) {
biggestSumSoFar = currentSum;
biggestSubListSoFar = currentSubList;
}
}
}
return biggestSubListSoFar;
}
private List<Integer> subListSum(final List<Integer> nums, final int left, final int right)
{
final List<Integer> sublist = new ArrayList<>();
for (int i = left; i < right; i++)
{
sublist.add(nums.get(i));
}
return sublist;
}
private int sum(List<Integer> arr) {
int sum = 0;
for(int a : arr){
sum += a;
}
return sum;
}

Answer 2

添加第三个内部for循环可以使任务变得更容易。想想你会如何用纸和笔来完成它。假设您有一个由6个元素组成的数组，其索引从0到ArrayList0，那么所有可能的子数组都将具有以下起始索引和结束索引(包括strat，不包括end(

0 - 1     1 - 2     2 - 3     3 - 4     4 - 5
0 - 2     1 - 3     2 - 4     3 - 5   
0 - 3     1 - 4     2 - 5   
0 - 4     1 - 5   
0 - 5 

有了以上所有你需要的是计算包含并存储相关的开始和结束指数

public List<Integer> solution(List<Integer> nums) {
int maxSubArrSum = Integer.MIN_VALUE;
int start = 0;
int end   = 0;
for (int left = 0; left < nums.size(); left++){
for (int right = left+1; right < nums.size(); right++){
int subSum = 0;
for (int k = left; k < right; k++){
subSum += nums.get(k);
}
if (subSum > maxSubArrSum){
maxSubArrSum = subSum;                    
start = left;
end   = right;
}
}
}
return nums.subList(start,end);
}

Answer 3

你的方法很安静。最后一部分有两个问题：

1. int greatest = Integer.MAX_VALUE;应改为Integer.MIN_VALUE
2. 检查子阵列的大小，但必须检查子阵列之和

如果您将最后一部分更改为：

int greatest = Integer.MIN_VALUE;
for (int i = 0; i < lists.size(); i++) {
if (sum(lists.get(i)) > greatest) {
greatest = lists.get(i).size();
smallest = i;
}
}

利用

public static int sum(List<Integer> arr) {
int sum = 0;
for(int a : arr){
sum += a;
}
return sum;
}

它产生了期望的结果。

Answer 4

这里是Kadane算法的修改版本，用于查找列表中连续元素的最大和。它改编自Python中给出的解决方案，只需一次通过即可工作

List<Integer> list = List.of(-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18);
List<Integer> subList = maxSubArray(list); 
System.out.println(subList);

打印

[17, 0, 0, 9, 20, 7]
public static List<Integer> maxSubArray(List<Integer> list) {
int max = Integer.MIN_VALUE;
int sum = max;
int end = 0;
int cstart = 0, start = 0;
for (int i = 0; i < list.size(); i++) {
int val = list.get(i);
if (sum <= 0) {
sum = val;
cstart = i;
} else {
sum += val;
}
if (sum > max) {
max = sum;
start = cstart;
end = i;              
}
}
return list.subList(start,end+1); 
}

Answer 5

基本上，您试图使用蛮力算法来处理此任务，在更糟糕的情况下，该算法将具有O(n^2(的时间和空间复杂性。

它可以用线性(即O(n((的时间和空间复杂性来完成，而不需要嵌套循环。

使用这种方法，首先，我们需要使用Kadane算法找到子阵列的最大可能和。

然后在跟踪当前和的单个循环中对源列表执行迭代。当它等于最大和时，意味着找到了连续元素的目标子阵列。

变量start和end表示结果子阵列的开始和结束索引。

方法subList()在源列表上创建一个视图，并且对视图的每次修改都将反映在源中，反之亦然。因此，作为预防措施，它被一个新的ArrayList实例所包裹。

public static List<Integer> solution(List<Integer> nums) {
if (nums.size() == 0) {
return Collections.emptyList();
}
final int maxSum = getMaxSum(nums); // getting max sum by using Kadane's algorithm
int curSum = nums.get(0);
int start = 0; // beginning of the resulting subarray
int end = 0; // end of the resulting subarray exclusive
for (int i = 1; i < nums.size(); i++) {
if (curSum == maxSum) {
end = i;
break; // maximus sub-array was found
}
if (nums.get(i) > curSum + nums.get(i)) {
start = i;             // setting start to current index
curSum = nums.get(i);  // assigning the current element the sum
} else {
curSum += nums.get(i); // adding the current element to the sum
}
}
return new ArrayList<>(nums.subList(start, end));
}

Kadane的算法实现。

总体思路是保持两个变量，表示全局和局部最大值。局部最大值在每次迭代中都会发生变化，我们要么

• 将当前元素添加到局部最大值
• 或者将当前元素的值分配给局部最大值

在每次迭代结束时，将全局最大值与局部最大值进行比较，并根据需要进行调整。

public static int getMaxSum(List<Integer> nums) {
int maxSum = Integer.MIN_VALUE;
int curSum = nums.get(0);
for (int i = 1; i < nums.size(); i++) {
curSum = Math.max(nums.get(i), curSum + nums.get(i));
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
}

main()

public static void main(String[] args) {
List<Integer> source = List.of(-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18);
System.out.println(solution(source));
}

输出

[17, 0, 0, 9, 20, 7]