使用2个线程查找数组中连续整数的最大和

Question

我想用2个线程找到数组中连续整数的最大和。

单线程非常简单

int maxSum = Integer.MIN_VALUE;
public static void main(String[] args) {
MaxSumSubArray maxSumSubArray = new MaxSumSubArray();
maxSumSubArray.maxSum(new int[]{1, 2, 3, -12, 7, 9,3} , 0);
System.out.println(maxSumSubArray.maxSum);
}
public int maxSum(int[] nums, int index){
int maxSumForCurrentIndex = 0;
if (index == nums.length - 1)
maxSumForCurrentIndex = nums[index];
else
maxSumForCurrentIndex = Math.max(nums[index], nums[index] + maxSum(nums, index + 1));
maxSum = Math.max(maxSum, maxSumForCurrentIndex);
return maxSumForCurrentIndex;
}

我可以创建两个线程，一个具有偶数索引，另一个具有奇数索引，然后将结果存储在MaxHeap中并获得第一个元素。

有更好的方法吗？

我已经试着做代码了。像这样的东西。但它没有给我正确的答案。

public static void main(String[] args) throws InterruptedException {
MaxSumSubArray maxSumSubArray = new MaxSumSubArray();
int[] nums = {1, 2, 3, -12, 7, 9, 3};
int[] answer = new int[nums.length];
for(int i = 0;i<answer.length; i = i+1){
MaxSum m1=new MaxSum(nums, 0);
m1.start();
m1.join();
answer[i] = m1.answer;
}
for(int i = 1;i<answer.length; i = i+2){
MaxSum m2=new MaxSum(nums, i);
m2.start();
m2.join();
answer[i] = m2.answer;
}
System.out.println(Arrays.toString(answer));
System.out.println(Arrays.stream(answer).max().getAsInt());
}

class MaxSum extends Thread{
int[] nums;
int index;
int answer;
MaxSum(int[] nums, int index){
this.nums = nums;
this.index = index;
this.answer = Integer.MIN_VALUE;
}
@Override
public void run() {
int maxSumForCurrentIndex = 0;
if(index == nums.length - 1){
maxSumForCurrentIndex = nums[index];
} else {
MaxSum m1 = new MaxSum(nums, index + 1);
m1.start();
try {
m1.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
answer = Math.max(nums[index], nums[index] + m1.answer);
maxSumForCurrentIndex = answer;
}
}
}

Answer 1

您可以让一个线程从左向右，而另一个线程则从右向左。当线程经过数组的中间并找到一个负数时，线程会中断。然后从两个结果中取max。

在最坏的情况下，两个线程都将浏览整个数组，因此您不会得到任何加速。另一方面，如果很大百分比的数字是负数，这将使您的速度提高2倍(假设数组足够大，运行两个单独的线程是有意义的(。