目录
- 最大子数组问题
- 矩阵乘法的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)
