Find largest sum of consecutive integers in array using 2 threads

Viewed 155

I want to find the largest sum of consecutive integers in an array using 2 threads.

It is quite simple with a single thread

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

I can create two threads one with an even index and one with an odd index, then store the results in the MaxHeap and get the first element.

Is there a better approach to do this?

I have tried to do the code. Something like this. But it didn't give me the correct answer.

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

    }
}


1 Answers

You can have one thread go from left to right while the other one from right to left. The threads break when they pass the middle of the array and find a negative number. Then you take max from both the results.

In the worst case both threads will browse the entire array, so you won't get any speedup. On the other hand, if a large percentage of numbers is negative this should give you up to 2x speedup (assuming the array is large enough, that it makes sense to run two separate threads).

Related