最小方差划分_如何找到最小的方差区间

给一个数组，求一个k值，使得前k个数的方差 + 后面n-k个数的方差最小

解题思路：
如果不考虑方差的概念，这题可以简化为 “给一个数组，求一个k值，使得前k个数的和 + 后面n-k个数的和最小”。

举例， 如 nums = [1,3,2,4]，我们可以先从左向右求出各个子段和 [1,4,6,10]，然后再从右向左求出各个子段和 [4,6,9,10]，我们发现对应的子段和为 1 -> 9, 4 -> 6, 6 -> 4。因此，我们只需要正反遍历数组两次，就可以求得结果。

时间复杂度：O(n)，空间复杂度 O(n)

方差概念：平方的均值减去均值的平方，即 D(X) = E(x^2) - [E(X)]^2

class Solution:
    """
    @param nums: 数组
    @return: 最小方差划分的数组索引和最小方差
    """
    def minVariancePartition(self, nums):
        left = self.subVariance(nums[:])
        right = self.subVariance(nums[::-1])[::-1]
        minVariance, index = float("inf"), 0
        for i in range(1, len(right)):
            if left[i-1] + right[i] < minVariance:
                minVariance = left[i-1] + right[i]
                index = i - 1  # 更新划分的索引
        return index, minVariance

    def subVariance(self, nums):
        subVar = []
        subSum = subSquare = 0
        for i in range(len(nums)):
            subSum += nums[i]
            subSquare += nums[i] * nums[i]
            subVar.append(subSquare/(i+1) - (subSum/(i+1))**2) # 子数组方差
        return subVar

a = [4,3,1,2]
print(Solution().minVariancePartition(a)) # (1,1.25)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26