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.