题目：给出一个指定整形数组，求从数组某下标开始连续求和的”最大值“，并给出”起始“及”结束“的下标
如：给定数组[-1，8，-6，7，-10，-3，3，2] 那么连续求和最大值是7，开始下标是1、结束是3，即是[8,-6,7]的和。
思路：
从数组起始位置向后遍历，抛弃和为负数的子数组，加上和为正数的子数组。（想象一个滑动窗口不停向右移动）
代码:
type Response struct {
Start int
End int
MaxSum int
}
func CaculateMaxSum(numlist []int) Response {
switch len(numlist) {
case 0:
return Response{-1, -1, 0}
case 1:
return Response{0, 0, numlist[0]}
default:
}
sum := numlist[0]
sumToCurrent := numlist[0]
start, end := 0, 0
for index, num := range numlist {
//abando negative sum
if sum < 0 && num > sum {
start, end, sum = index, index, num
sumToCurrent = num
} else if sum > 0 && (sumToCurrent-sum)+num > 0 {
//sum the current value
start, end, sum = start, index, sumToCurrent+num
sumToCurrent = sum
} else {
//update sumToCurrent
sumToCurrent = sumToCurrent + num
}
}
return Response{start, end, sum}
}
func TestCaculateMaxSum(t *testing.T){
testlist := [][]int{
[]int{-1, 8, -7, 6, -10, -3, 3, 2},
[]int{-8, -7, -6, -10, -3, -5},
[]int{-8, -7, 6, -1, -3, 5},
}
for _, numlist := range testlist {
rsp := CaculateMaxSum(numlist)
t.Logf("start:%v, end:%v, sum:%v\n", rsp.Start, rsp.End, rsp.MaxSum)
}
}
