最大子序列和问题

2017/08/07

最大子序列和问题

问题

最大子序列和问题:

给定整数$A_1$,$A_2$,…,$A_n$(可能有负数),求$ \sum{^j_{k=i}}A_k$的最大值

(为方便起见,如果所有整数都是负数,则明天子序列和为0)

四个算法和时间复杂度

算法 时间复杂度
算法一 $O(N^3)$
算法二 $O(N^2)$
算法三 $O(NlogN)$
算法四 $O(N)$

算法一

三重循环。

前两个循环是列出所有可能的子序列,i, j分别指向子序列的头和尾。

第三个循环是对子序列进行求和。

func function1(a []int) int {
	n := len(a)
	maxSum := 0
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			tempSum := 0
			for k := i; k <= j; k++ {
				tempSum += a[k]
			}
			if tempSum > maxSum {
				maxSum = tempSum
			}
		}
	}
	return maxSum
}

算法二

func function2(a []int) int {
	n := len(a)
	maxSum := 0
	for i := 0; i < n; i++ {
		tempSum := 0
		for j := i; j < n; j++ {
			tempSum += a[j]
			if tempSum > maxSum {
				maxSum = tempSum
			}
		}
	}
	return maxSum
}

算法三

func function3Sum(a []int, leftIndex, rightIndex int) int {
	maxSum := 0
	if leftIndex == rightIndex {
		if a[leftIndex] > 0 {
			maxSum = a[leftIndex]
		}
		return maxSum
	}

	var centerIndex int
	centerIndex = (leftIndex + rightIndex) / 2
	leftMaxSum := function3Sum(a, leftIndex, centerIndex)
	rightMaxSum := function3Sum(a, centerIndex+1, rightIndex)

	leftSectionMaxSum := 0
	leftSectionSum := 0
	for i := centerIndex; i >= 0; i-- {
		leftSectionSum += a[i]
		if leftSectionSum > leftSectionMaxSum {
			leftSectionMaxSum = leftSectionSum
		}
	}
	rightSectionMaxSum := 0
	rightSectionSum := 0
	for i := centerIndex + 1; i < rightIndex; i++ {
		rightSectionSum += a[i]
		if rightSectionSum > rightSectionMaxSum {
			rightSectionMaxSum = rightSectionSum
		}
	}

	return int(math.Max(math.Max(float64(leftMaxSum), float64(rightMaxSum)), float64(leftSectionMaxSum+rightSectionMaxSum)))
}

func function3(arr []int) int {
	return function3Sum(arr, 0, len(arr)-1)
}

算法四

该算法的一个优点就是,数据一旦被扫描,就不需要在此记忆

是联机算法:在任何时刻,该算法都能对它已经读取的数据,给出子序列的最大值的正确答案

只需要常量空间,以线性时间允许的,联机算法,几乎是完美的算法

func function4(a []int) int {
	n := len(a)
	maxSum := 0
	tempSum := 0
	for i := 0; i < n; i++ {
		if tempSum < 0 {
			tempSum = 0
		}
		tempSum += a[i]

		if tempSum > maxSum {
			maxSum = tempSum
		}
	}
	return maxSum
}

算法的结果和运行时间

func genArray(count int) []int {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	a := []int{}
	for i := 0; i < count; i++ {
		a = append(a, r.Intn(500)-250)
	}
	return a
}

func runGetMaxSum(f func([]int) int, a []int) {
	t := time.Now()
	maxSum := f(a)
	fmt.Println(time.Since(t), maxSum)
}

func main() {
	t0 := time.Now()
	a := genArray(3000)
	fmt.Println(time.Since(t0))

	runGetMaxSum(function1, a)
	runGetMaxSum(function2, a)
	runGetMaxSum(function3, a)
	runGetMaxSum(function4, a)
}
140.44µs
2.279837401s 9560
4.8763ms 9560
8.076376ms 9560
8.059µs 9560