Finding Maximum Subarray, contiguous and non-contiguous

Problem: 

Given an array  of  elements, find the maximum possible sum of a

1. Contiguous sub-array
2. Non-contiguous (not necessarily contiguous) sub-array.

Empty sub-arrays/sub-sequences should not be considered.

Solution:

Below is the solution for the problem.

Algorithm 
For maximum contiguous elements sum

1) Make sum and previous_sum equal to first element in arrays, a[0]. 

Now we have to make sure that if sum is negative and Next element is positive, make sum = next element, else add next element to sum. This is done in step 2.

2) Let us assume next element is N, If sum < 0 and N > 0, make sum = N, else make sum = sum + N.

If sum is larger than previous sum, update the previous sum, else if sum < previous sum, and also sum < 0, make sum = next element. This is step 3.

3) If sum >= previous_sum, make previous_sum = sum, else if sum < 0, make sum = N.

4) Repeat steps 2 and 3 for all the elements of input array.

5) Take maximum of sum and previous_sum as the result

For maximum non contiguous elements sum

1) Make sum equal to first element in arrays, a[0]. 

2) If sum is less than 0 and next element, say N is greater than or equal to 0, make sum =N, else,

3) If sum + N > sum, make sum = sum + N, else,

4) If (sum + N < sum) and (sum < N), make sum = N.

5) Repeat step 2, 3 and 4 for each element in the array.

Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

public class ContiguousArraySum { /** * @param a input array * @param n number of elements in the array * @return returns the array of size 2, element at 0 gives sum of contiguous elements * while element at 1 gives sum of non-contiguous elements. */ private static long[] findSum(int[] a, int n) { long[] result = new long[2]; long contSum = a[0]; long prevContSum = a[0]; long nonContSum = a[0]; for (int i = 1; i < n; i++) { if (contSum < 0 && a[i] >= 0) { contSum = a[i]; } else { contSum += a[i]; } if (nonContSum < 0 && a[i] >= 0) { nonContSum = a[i]; } else if (nonContSum + a[i] > nonContSum) { nonContSum += a[i]; } else if (nonContSum < a[i] && nonContSum + a[i] < nonContSum) { nonContSum = a[i]; } if (contSum >= prevContSum) { prevContSum = contSum; } else if (contSum < 0) { contSum = a[i]; } } result[0] = contSum > prevContSum ? contSum : prevContSum; result[1] = nonContSum; return result; } }

Please post in the comment section if any thing in code is not clear.

Read More

Implement binary search algorithm in Java

A binary search algorithm assumes the input array to be sorted and finds the position of a specified value within that array. In each step, the algorithm compares the search value with value at the middle element of the array. If it match, then a matching element has been found so its index, or position, is returned. Otherwise, if value is less than the middle element's value, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right.

Worst case performance: O(log n)

Best case performance: O(1)

Assumption: Input array is sorted

public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
        int[] inputArray = { 1, 3, 6, 8, 12, 23, 29, 31, 46, 59, 77, 81, 95 };
        int searchInt = 3;
        System.out.println("Position for " + searchInt + " is "
                + binarySearch.binarySearch(inputArray, searchInt));
    }

    public int binarySearch(final int[] inputArr, final int key) {
        int startIndex = 0;
        int endIndex = inputArr.length - 1;
        while (startIndex <= endIndex) {
            
            // Search for key at mid index, if found return the index.
            int mid = (startIndex + endIndex) / 2;
            if (key == inputArr[mid]) {
                return mid;
            }
            
            // if key is not found, update the start and end index
            if (key < inputArr[mid]) {
                endIndex = mid - 1;
            } else {
                startIndex = mid + 1;
            }
        }
        return -1;
    }

}

Output:

Position for 3 is 1

Hope you liked the above post, connect at +Java Territory to stay updated with latest articles.

Read More

Sieve of Eratosthenes algorithm: Efficient way to find prime numbers

First, lets find prime numbers in following manner, which tries to divide each number, say n, by each integer i, where 2<= i <= n/2.

Below code finds the prime numbers between 2 and 10,00,000.

    private static void findPrime() {
        int count = 0;
        int num = 1000000;
        for (int i = 2; i <= num; i++) {
            count = 0;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    count++;
                    break;
                }
            }
            if (count == 0) {
                System.out.println(i);
            }
        }
    }

Above code took 64 seconds (64,575 msecs) when executed on my machine.

Now following is the Java implementation of Sieve of Eratosthenes algorithm to find prime numbers.
It assumes each number to be prime and then tries to eliminate the non-prime ones. Below is the java implementation:

    public static void findPrimeBySieve() {
        int num = 1000000;
        // initially assume all integers are prime
        boolean[] isPrime = new boolean[num + 1];
        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i * i <= num; i++) {

            // if i is prime, then mark multiples of i as nonprime
            // suffices to consider mutiples i, i+1, ..., N/i
            if (isPrime[i]) {
                for (int j = i; i * j <= num; j++) {
                    isPrime[i * j] = false;
                }
            }
        }

        // count primes
        int primes = 0;
        for (int i = 2; i <= num; i++) {
            if (isPrime[i]){
                System.out.println(i);
                primes++;
            }
        }
        System.out.println("The number of primes <= " + primes);
    }

Execution time of above code was only 0.5 seconds (529 msecs) on my machine, i.e., 128 times faster for finding prime numbers between 2 and 1000000.

Hope you liked the post. Connect at +Java Territory  to stay tuned with latest updates.

Read More

Optimizing Bubble Sort Algorithm

Having been in Java world for around 5 years, I believe Bubble Sort is the probably simplest and widely used sorting algorithm that works by repeatedly swapping the adjacent elements if they are not in the right order. However, with just a little tweaking, it’s possible to make it more efficient. So, we will first see what Bubble Sort algorithm is and then move to its optimization part.

To sort the entire array, the array is traversed n-1 time (array having n elements). These are called passes. In the first pass the largest element moves to the last position (sorting in ascending order). So if the original (unsorted) array is:

55           33           99           77           44

During the first iteration, adjacent elements will be compared, and swapped if larger element is on left side), as shown below:

After first iteration, the largest element is at the last position.

33          55        77          44         99

Now, in the 2nd pass, we will consider the first (n-1) elements only (because last position already has largest element). After 2nd pass the array will be

33           55           44           77           99

i.e., 77 will be moved to the (n-1)th position. 

After (n-1) iterations, (n-1) elements will be moved to their proper positions, the last element has to be the smallest. So the array will be sorted after n-1 passes.

Algorithm:

void bubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

              for (int j = 0; j < n - i - 1; j++) {

                     if (array[j] > array[j + 1]) {

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

       }

}

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Improvement (Optimization):

In the above example, the array got sorted after 2nd pass, but we will still continue with the 3rd, 4th pass. Suppose if the array is already sorted, then there will be no swapping (because adjacent elements are always in order), but still we will continue with the passes and there will still be (n-1) passes.

If we can identify, that the array is sorted, then we should stop execution of further passes. This is the optimization over the original bubble sort algorithm.

If there is no swapping in an iteration pass, it means the array has become sorted, so algorithm should be smart enough to skip further iterations.

For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.

void optimizedBubbleSort(int array[], int n) {

       for (int i = 0; i < n; i++) {

              boolean flag = true;

              for (int j = 0; j < n - i - 1; j++) {

                     if (array[j] > array[j + 1]) {

                           flag = false;

                           int temp = array[j + 1];

                           array[j + 1] = array[j];

                           array[j] = temp;

                     }

              }

              // No Swapping happened, array is sorted

              if (flag) {

                     return;

              }

       }

}

For the best case (array already sorted) the optimized algorithm will be O(n).

For average case also, the performance will see an improvement. Whereas the original algorithm was O(n²) for all the cases.

Read More