分治策略

递归

Posted by Jow on June 24, 2019

目录

  1. 最大子数组问题
  2. 矩阵乘法的Srassen算法

Escape from shenzhen not due to is unfair, only because you are not try your best.

最大子数组问题

从现实问题股票的购入和出售,应该在什么时候购入然后什么时候卖出,这个时候我们可以将数据进行转换,算出价格的和前一天的变化,要想获得最大的利益,则需要算出在一段时间内,变化值相加最大的那一段。抽象出数学描述,如下:

在一传数组中找到差值最大的子串。这里有两种解法,一种是暴力解法,求出数组中的全组合,然后进行比较判断,时间复杂度是n的平方。第二种使用分治策略。

在这个数组中只有存在负数才是有意义的,否则整个数组都是最大子串。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
local arr = { 13, -3, -25, 20, -3, 16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 }


local function findMaxCrossingSubArray(A, low, mid, high)
    local leftSum = math.mininteger
    local sum = 0
    local maxLeft = low
    for i = mid, low, -1 do
        sum = sum + A[i]
        if sum > leftSum then
            leftSum = sum
            maxLeft = i
        end
    end
    local rightSum = math.mininteger
    sum = 0
    local maxRight = mid + 1
    for i = mid + 1, high do
        sum = sum + A[i]
        if sum > rightSum then
            rightSum = sum
            maxRight = i
        end
    end
    return maxLeft, maxRight, leftSum + rightSum
end

local findMaximumSubArray
findMaximumSubArray = function(A, low, high)
    if low == high then
        return low, high, A[low]
    else
        local mid = math.floor((low + high) / 2)
        local leftLow, leftHigh, leftSum = findMaximumSubArray(A, low, mid)
        local rightLow, rightHigh, rightSum = findMaximumSubArray(A, mid + 1, high)
        local crossLow, crossHigh, crossSum = findMaxCrossingSubArray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum then
            return leftLow, leftHigh, leftSum
        elseif rightSum >= leftSum and rightSum > crossSum then
            return rightLow, rightHigh, rightSum
        else
            return crossLow, crossHigh, crossSum
        end
    end
end

local i, j, sum = findMaximumSubArray(arr, 1, #arr)