Problem: 53. 最大子数组和

• 思路
• 解题方法
• 复杂度
• Code
• Code

思路

双指针 但是用count保存双端的值 哪端count小哪端移动

解题方法

描述你的解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

// 这版性能一般
func maxSubArray(nums []int) int {
	resultArray := nums[:]
	leftIndex, rightIndex := 0, len(nums)-1
	// leftStart, rightStart := leftIndex, rightIndex
	leftCount, rightCount := nums[leftIndex], nums[rightIndex]

	for {
		// 当数组足够小直接退出,不用分
		if len(nums) == 1 {
			return nums[0]
		}

		// 判断下标距离, 如果下标相邻直接退出
		if leftIndex+1 == rightIndex {
			break
		}

		// 移动小的那端
		if leftCount < rightCount {
			leftIndex++
			if leftCount < 0 {
				resultArray = resultArray[leftIndex:]
				// 数组变化时leftIndex要缩小,leftIndex归为0
				rightIndex -= leftIndex
				leftIndex = 0
				leftCount = resultArray[leftIndex]
			} else {
				leftCount += resultArray[leftIndex]
			}
		} else {
			rightIndex--
			if rightCount < 0 {
				// 数组变化时rightIndex++
				resultArray = resultArray[:rightIndex+1]
				rightCount = resultArray[rightIndex]
			} else {
				rightCount += resultArray[rightIndex]
			}
		}

	}
	return max(leftCount+rightCount, max(leftCount, rightCount))
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

Code

// 将消耗比较大的切片去掉 性能已经不错了
func maxSubArray(nums []int) int {
	// 当数组足够小直接退出,不用分
	if len(nums) == 1 {
		return nums[0]
	}
	leftIndex, rightIndex := 0, len(nums)-1
	leftCount, rightCount := nums[leftIndex], nums[rightIndex]

	for {
		// 判断下标距离, 如果下标相邻直接退出
		if leftIndex+1 == rightIndex {
			break
		}
		// 移动小的那端
		if leftCount < rightCount {
			leftIndex++
			if leftCount < 0 {
				// 小于0舍弃掉并换成当前值
				leftCount = nums[leftIndex]
			} else {
				leftCount += nums[leftIndex]
			}
		} else {
			rightIndex--
			if rightCount < 0 {
				// 小于0舍弃掉并换成当前值
				rightCount = nums[rightIndex]
			} else {
				rightCount += nums[rightIndex]
			}
		}
	}
	return max(leftCount+rightCount, max(leftCount, rightCount))
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}