最大子数组算法

Question

我打算使用下面的函数来检测给定数组的最大子数组，但是，我需要检测到的最大子数组的开始和结束下标。我如何实现它们，以便它们给我检测到的最大子数组的开始和结束?

谢谢。

int maxSubarraySum (int A[], int low, int high)
{
if (low == high)
return A[low]
else
{
int mid = low + (high - low)/2
int left_sum = maxSubarraySum (A, low, mid)
int right_sum = maxSubarraySum (A, mid+1, high)
int crossing_Sum = maxCrossingSum(A, low, mid, high)

return max (left_sum, right_sum, crossing_Sum)
}
}

int maxCrossingSum(int A[], int l, int mid, int r)
{
int sum = 0
int lsum = INT_MIN
for(i = mid to l)
{
sum = sum + A[i]
If (sum > lsum)
lsum = sum
}
sum = 0
int rsum = INT_MIN
for(i = mid+1 to r)
{
sum = sum + A[i]
If (sum > rsum)
rsum = sum
}
return (lsum + rsum)
}

Answer 1

在maxSubarraySum()中的返回语句之前，检查left_sum, right_sum和crossing_Sum之间哪个是最大的，然后用一个全局变量检查当前获得的最大值。如果新的max更高，那么将新的max以及开始和结束索引保存在另外两个全局变量中。这不是一个干净的解决方案，但可以解决问题!