Maximum subarray problem - Kadane algorithm (Solution in Java).

In Maximum subarray problem we are given one-dimensional array of numbers and in that array we have to find a contiguous subarray such that when we add all numbers of subarray the sum should be greater than sum of numbers of any other subarray within that array.  For example, in array {2,1,-4,5,-2,8,1,-2}
the subarray {5,-2,8,1} has sum=12 and that sum is maximum than all other subarrays.
This problem can be solved using varoius methods like brute force method O(N^2) or divide and conquer (nlogn).
But by using Kadane algorithm we can solve this problem in linear time O(N).

Note that this problem is interesting to solve only when array has both negative and positive numbers. Because if all elements of array are positive than subarray having maximum sum is complete array itself.
For example
5,0,1,2,7,2
maximum sum is 17 that is of complete array.
Also array should contain atleast one positive number to ensure that there is subarray with maximum sum.
Below program gives maximum value of sum of subarray numbers.

Java code:
class Main {
   
    static int kadane(int [] array){
        int max_ending_here = 0, max_so_far = 0;
        for (int i = 0; i < array.length; i++) {
            max_ending_here+=array[i];
            if(max_ending_here < 0){
                max_ending_here = 0;
            }else if(max_ending_here > max_so_far){
                max_so_far = max_ending_here;
            }
        }
        return max_so_far;
    }
   
    public static void main(String[] args) {
        int maxSum = kadane(new int[]{2,-3,4,-1,-2,1,5,-3});
        System.out.println("Maximum sum of subarray="+maxSum);
    }
}

Output:
Maximum sum of subarray=7

Explanation:
In kadane algorithm we take two int variables max_ending_here, max_so_far both initialized to 0 . In each iteration of for loop we add number at current index to max_ending_here and after that we check:
1. If max_ending_here becomes less than zero we reset max_ending_here back to zero.
2. Else if it greater than max_so_far we set max_so_far to max_ending_here.

So whenever max_ending_here becomes negative we reset it to zero because negative number will only reduce overall sum and previous maximum value of max_ending_here before it becomes negative is saved in max_so_far variable and max_so_far is changed only when max_ending_here becomes greater than max_so_far. Thus we compute maximum at each position.

Above program can be easily modified to find subarray having maximum sum.

Java code:

class Main {
   
    static int kadane(int [] array){
        int max_ending_here = 0, max_so_far = 0;
        int startIndex = 0, endIndex = 0, tmpStart = 0;       
      for (int i = 0; i < array.length; i++) {
            max_ending_here+=array[i];
            if(max_ending_here < 0){
                max_ending_here = 0;
                tmpStart = i + 1;
            }else if(max_ending_here > max_so_far){
                max_so_far = max_ending_here;
                startIndex = tmpStart;
                endIndex = i;
            }
        }
        if(startIndex <= endIndex){
            System.out.println("Subarray starts at startIndex="+startIndex+" and ends at endIndex="+endIndex);
            System.out.print("Subarray is:");
            for (int i = startIndex; i <= endIndex; i++) {
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }else{
            System.out.println("All numbers in array are negative or zero.");
        }
       
        return max_so_far;
    }
   
    public static void main(String[] args) {
        int maxSum = kadane(new int[]{2,-3,4,-1,-2,1,5,-3});
        if(maxSum > 0){
            System.out.println("Maximum sum of subarray="+maxSum);
        }
    }
}
Output:
Subarray starts at startIndex=2 and ends at endIndex=6
Subarray is:4 -1 -2 1 5
Maximum sum of subarray=7

Three new variables are introduced tmpStart, startIndex and endIndex to track subarray start and end position in array and both are initialised to 0. tmpStart is set to value of next index in array when max_ending_here becomes less than zero and startIndex is set to value of tmpStart in else condition.

Value of variables during course of program is listed in below table:

Printing odd, even number alternately using two threads in Java.

This is my first post and I am going to start with a multi-threading problem in Java. The problem statement is there are two threads, lets name them EvenThread & OddThread. By using these two threads print an output such that first OddThread prints odd number and after that EvenThread prints even number and again OddThread prints odd number and so on. For example sample output

OddThread prints 1
EvenThread prints 2
OddThread print 3
and so on.

Both threads should operate upon common int variable to print even & odd output. I am going to post  solution that uses Java synchronized block,  wait() and notify() method to achieve result such that both threads prints odd even number alternately. Explanation is given below.

Java code:
class Main {
      
    public static void main(String[] args) {
        Counter counter = new Counter();//it will be used for locking.
        new Thread(new EvenTask(counter), "Even Thread").start();
        new Thread(new OddTask(counter), "Odd Thread").start();
    }
}

class Counter{
    //The int variable that is used by both threads.
    public int count = 1;
}

class EvenTask implements Runnable{
    private Counter counter;
  
    public EvenTask(Counter counter){
        this.counter = counter;
    }
  
    @Override
    public void run() {
        while (true) {
            synchronized (counter) {
                //If counter.num is odd then even thread will release lock and goes to wait state
                //so that odd thread can print.
                if(counter.count % 2!=0){
                    try {
                        counter.notify();
                        counter.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                //Control will come here if odd thread has released lock
                //or if number is even.
                System.out.println(Thread.currentThread().getName()+"-"+counter.count);
                counter.count++;
                try {
                    Thread.sleep(200);//Some ms of sleep so that output is not very fast.
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

class OddTask implements Runnable{
    private Counter counter;
  
    public OddTask(Counter counter){
        this.counter = counter;
    }
  
    @Override
    public void run() {

        while (true) {
            synchronized (counter) {
                //If counter.num is even then odd thread will release lock and goes to wait state
                //so that even thread can print.
                if(counter.count % 2==0){
                    try {
                        counter.notify();
                        counter.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                //Control will come here if even thread has released lock
                //or if number is odd.
                System.out.println(Thread.currentThread().getName()+"-"+counter.count);
                counter.count++;
                try {
                    Thread.sleep(200);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

In main method while creating EvenTask and OddTask runnable, object of Counter class is passed to constructor of both classes. This shared counter object is used for locking and also it has int variable count that is shared between both threads for printing odd/even number. Counter class int variable count is initialized to 1.

Inside run method of EvenTask there is if condition that check if count has odd value. If count has odd value then notify() is called which wakes up OddThread and after that wait(); is called which makes current thread i.e. EvenThread goes to waiting state. After OddThread wakes up it acquire lock (which is released by EvenThread) and print odd number and after that increment of count when next time if condition run count is even and code inside if condition of OddTask run and notify() and wait methods are called and this process keeps on repeating.

//if condition code from EvenTask
                if(counter.num % 2!=0){
                    try {
                        counter.notify();
                        counter.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }

Similarly in OddTask we check if count has even value then waiting thread is notified and current thread (i.e. OddThread) goes to waiting state. If count is odd inside OddTask then code inside if condition does not run and odd number is printed.

I did not make Counter class instance variable count volatile because count variable read/write happens in synchronized context of both two threads and variable is not modified else where.

Since there are only two threads involved I have used notify() instead of notifyAll().