# 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 +
'}';
}
}```

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 < A.length; i++) {
if (sum == 0 && A[i] <= 0) {
start = i + 1;
continue;
}
sum += A[i];
if (sum > result) {
end = i;
result = sum;
}
if (sum < 0) {
start = i + 1;
sum = 0;
}

}
return new SubArrayResult(result, start, end);
}```

OK, what algorithm is doing:

– firstly run throughout all array

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

– skipping negative values and move start index

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

– just add next value to current sum

`sum += A[i];`

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

```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 < 0) {
start = i + 1;
sum = 0;
}```

So, that is all 🙂