Algorithm {The maximum-subarray problem}

I’ve just opened Introduction to Algorithms on Divide-and-Conquer chapter, and found interesting item – The maximum-subarray problem. In book you can find implementation with complexity O(NlogN) with good explanation, but in Exercises part there is good task:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1<=i<=j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j .

So, That is easy, because there are some ideas, you just need to stop and think a bit and all will be clear …

As described in the book you need to return 3 params
– max sum
– start index of sub array
– end index of sub array

OK, lets go …

Firstly create return structure.

public class SubArrayResult {
        final long sum;
        final int startIndex;
        final int endIndex;
 
        private SubArrayResult(long sum, int startIndex, int endIndex) {
            this.sum = sum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
 
        public long getSum() {
            return sum;
        }
 
        public int getStartIndex() {
            return startIndex;
        }
 
        public int getEndIndex() {
            return endIndex;
        }
 
        @Override
        public String toString() {
            return "SubArrayResult{" +
                    "sum=" + sum +
                    ", startIndex=" + startIndex +
                    ", endIndex=" + endIndex +
                    '}';
        }
    }

public class SubArrayResult {

final long sum;

final int startIndex;

final int endIndex;

private SubArrayResult(long sum, int startIndex, int endIndex) {

this.sum = sum;

this.startIndex = startIndex;

this.endIndex = endIndex;

}

public long getSum() {

return sum;

}

public int getStartIndex() {

return startIndex;

}

public int getEndIndex() {

return endIndex;

}

@Override

public String toString() {

return "SubArrayResult{" +

"sum=" + sum +

", startIndex=" + startIndex +

", endIndex=" + endIndex +

'}';

}

After that try to create algorithm.

public SubArrayResult findMaximumSubArray(int[] A) {
        long sum = 0;
        long result = 0;
        int start = 0;
        int end = 0;
 
        for (int i = 0; i &lt; A.length; i++) {
            if (sum == 0 &amp;&amp; A[i] &lt;= 0) {
                start = i + 1;
                continue;
            }
            sum += A[i];
            if (sum &gt; result) {
                end = i;
                result = sum;
            }
            if (sum &lt; 0) {
                start = i + 1;
                sum = 0;
            }
 
        }
        return new SubArrayResult(result, start, end);
    }

public SubArrayResult findMaximumSubArray(int[] A) {

long sum = ;

long result = ;

int start = ;

int end = ;

for (int i = ; i < A.length; i++) {

if (sum == && A[i] <= ) {

start = i + 1;

continue;

}

sum += A[i];

if (sum > result) {

end = i;

result = sum;

}

if (sum < ) {

start = i + 1;

sum = ;

}

return new SubArrayResult(result, start, end);

}

OK, what algorithm is doing:

– firstly run throughout all array

for (int i = 0; i &lt; A.length; i++)

1	for (int i = ; i < A.length; i++)

– skipping negative values and move start index

if (sum == 0 &amp;&amp; A[i] &lt;= 0) {
   start = i + 1;
   continue;
}

if (sum == && A[i] <= ) {

start = i + 1;

continue;

}

– just add next value to current sum

sum += A[i];

1	sum += A[i];

– check if current sum > result value, if yes, assign sum to result and move end to current index

if (sum &gt; result) {
 end = i;
 result = sum;
}

if (sum > result) {

end = i;

result = sum;

}

– and last one if sum < 0 assign 0 to sum and move start to next index

if (sum &lt; 0) {
  start = i + 1;
  sum = 0;
}

if (sum < ) {

start = i + 1;

sum = ;

}

So, that is all 🙂

Leave a Reply Cancel reply