Content deleted Content added
m →Kadane's algorithm: note the possibility of returning the start and end indices of the maximum subarray |
No edit summary |
||
Line 18:
Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem, the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of [[dynamic programming]].
==Panov and Synkov's algorithm==
More efficient algorithm was invented by two russian programmers. It takes O(''n''lg(''n'')) operations.
<source lang="java">
private static int[] maxSubarray(int[] array,
int startIdx,
int endIdx)
{
final int len = endIdx - startIdx;
if (len < 2)
{
return new int[] {startIdx, endIdx, array[startIdx]};
}
final int midIdx = startIdx + len / 2;
final int[] left = maxSubarray(array, startIdx, midIdx),
right = maxSubarray(array, midIdx, endIdx);
int crossingMaxLeftStartIdx = midIdx - 1;
int crossingMaxLeft = array[crossingMaxLeftStartIdx];
int tmpSum = crossingMaxLeft;
for (int idx = crossingMaxLeftStartIdx - 1; idx >= startIdx; --idx)
{
tmpSum += array[idx];
if (tmpSum > crossingMaxLeft)
{
crossingMaxLeft = tmpSum;
crossingMaxLeftStartIdx = idx;
}
}
int crossingMaxRightEndIdx = midIdx + 1;
int crossingMaxRight = array[midIdx];
tmpSum = crossingMaxRight;
for (int idx = crossingMaxRightEndIdx; idx < endIdx; ++idx)
{
tmpSum += array[idx];
if (tmpSum > crossingMaxRight)
{
crossingMaxRight = tmpSum;
crossingMaxRightEndIdx = idx + 1;
}
}
final int crossingMax = crossingMaxLeft + crossingMaxRight;
int bestStartIdx = left[0],
bestEndIdx = left[1],
bestSum = left[2];
if (right[2] > bestSum)
{
bestStartIdx = right[0];
bestEndIdx = right[1];
bestSum = right[2];
}
if (crossingMax > bestSum)
{
bestStartIdx = crossingMaxLeftStartIdx;
bestEndIdx = crossingMaxRightEndIdx;
bestSum = crossingMax;
}
return new int[] {bestStartIdx, bestEndIdx, bestSum};
}
</source>
This function returns an array of three integers. First element is the start index of a maximum subarray, second one is the index of the subarray's last element +1, and third element contains the sum of the subarray. Note that there can be several max subarrays, the presented algorithm finds one of them.
==Generalizations==
| |||