# 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 🙂

## Read More Post

August 1, 2024

### Revolutionizing Your Ride: Expert Auto Service At Carolina Auto Service

February 27, 2024

January 25, 2024

January 25, 2024

January 24, 2024

January 19, 2024

01 Aug

27 Feb

25 Jan

25 Jan

24 Jan

19 Jan