本次代码用最大子数组问题（可参考算法导论， 即寻找数组arr中和最大的非空连续子数组，时间复杂度为O(nlogn)。
package main
func findmaxcrossarr(arr []int, low, high, mid int) (int, int, int) {
leftsum, rightsum := 0, 0
leftindex, rightindex, temp := 0, 0, 0
for i := mid; i >= low; i-- {
temp = temp + arr[i]
if temp > leftsum {
leftsum = temp
leftindex = i
}
}
temp = 0
for i := mid + 1; i <= high; i++ {
temp = temp + arr[i]
if temp > rightsum {
rightsum = temp
rightindex = i
}
}
return leftindex, rightindex, (leftsum + rightsum)
}
func findmaxsubarr(arr []int, low, high int) (int, int, int) {
if low == high {
return low, high, arr[low]
} else {
mid := int((low + high) / 2)
leftlow, lefthigh, leftsum := findmaxsubarr(arr, low, mid)
rightlow, righthigh, rightsum := findmaxsubarr(arr, mid+1, high)
crosslow, crosshigh, crosssum := findmaxcrossarr(arr, low, high, mid)
if leftsum >= rightsum && leftsum >= crosssum {
return leftlow, lefthigh, leftsum
}
if rightsum >= leftsum && rightsum >= crosssum {
return rightlow, righthigh, rightsum
} else {
return crosslow, crosshigh, crosssum
}
}
}
最终leftsum会得到原数组二分后左边数组的最大子数组。我们来看下过程。
首先执行到语句：
leftlow, lefthigh, leftsum := findmaxsubarr(arr, low, mid)后开始递归，每次执行到这句话，都会重新递归调用该函数。
也就是把数组arr不停二分取左边，直到只剩一个元素13，即递归到了最底层。
arr数组:
|
13 |
-3 |
-25 |
20 |
-3 |
-16 |
-23 |
18 |
返回13作为这一个元素的子数组的最大子数组。
即：leftlow, lefthigh, leftsum = 0, 0, 13
执行完该语句后，程序继续往下跑。开始执行最底层的右边数组。即：
rightlow, righthigh, rightsum := findmaxsubarr(arr, mid+1, high)同样返回-3，因为只有一个元素；同理跨越中间值的计算返回10。
比较这三个数，最终返回最13，即倒数第二层的leftsum = 13，继续计算倒数第二层的rightsum。
倒数第二层的right数组有两个元素，即-25,20，进行递归运算，在这次递归中，leftsum=-25,rightsum=20,crosssum=-5，所以最终返回到倒数第二层的rightsum=20，即三个数中的最大值。
这时我们已经获得了倒数第二层的leftsum和rightsum的值，程序继续运行求crosssum，并比较大小，将返回值赋值给leftsum（因为从这里开始不断递归）
到这里数组arr的二分数组中左边的数组已经计算完了，开始计算右边的，也就是从rightsum语句这里开始递归，所有的返回值都被赋值给rightsum，最终还得到右边数组的最大子数组。
最后计算crosssum，并返回最终的值。即20。
如果没有帮助，还请见谅。(Ｔ▽Ｔ)
转载自原文链接, 如需删除请联系管理员。
原文链接：【算法】关于递归函数返回值的理解。，转载请注明来源！