算法描述如下:
1)从第一行开始向下进行累加,累加和若大于之前的最大和,则记录此时的最大和及结束位置;
2)若累加和等于之前的最大和,但元素个数大于之前的最大和的元素个数,则记录此连续子矩阵的结束位置;
3)若累加和小于0,则重新开始记录;
4)若有符合条件的多个连续子矩阵,则输出最先找到的子矩阵。
小俞编写了一个实现该功能的VB程序,窗体加载时生成m*n个序列数据,依次存放在数组a,并显示在列表框List1中,在文本框Text1中输入该矩阵限定区域的左上角位置,在文本框Text2中输入右下角位置,单击“计算”按钮Command1后,找出连续和最大的子矩阵,在标签Label3上显示最大连续子矩阵和,在Label 4上显示该连续子矩阵的元素个数,在Label 5上显示该连续子矩阵开始与结束位置。程序运行界面如图所示。
Const m=12:Const n= 6
Dim a(1 Tom*n) As Integer
Private SubForm_Load()
‘生成m*n个数据,并显示在列表框List 1,代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, temp As Integer
Dim length As integer, begin As Integer, sum As Integer
Dim ks As String, js As String
Dim xy( 1 to 4) As Integer, h sum(1tom*n) As Integer
‘读取文本框Text 1的数值分别存储到数组xy(1)、xy(2),读取文本框Text 2的数值分别存储到数组xy(3)、xy(4),xy(1)、xy(3)表示所在行,xy(2)、xy(4)表示所在列,代码略
For i=1 To xy(3) -xy(1) + 1
h sum(i) = 0
Next i
‘求限定区域内每行数据之和
For i=1 To xy(3) -xy(1) + 1
For j= 1 To ①
h sum(i) =h sum(i) +a((xy(1) +i-2) *n+xy(2) +j-1)
Next j
Next i
‘找出最大连续之矩阵和
temp =0:sum=0:length=0:begin= 0
For i=1 To xy(3)-xy(1) + 1
If temp+h sum(i) >sum Then
sum=temp+h sum(i)
length=i-begin
k=i
ElseIf temp+h sum(i) =sum And ② Then
length=i-begin
k=i
End If
If temp+h sum(i) < 0 Then
begin=i
temp= 0
Else
temp=temp+h sum(i)
End If
Next i
ks=“(“ ③ ”+Str(xy(2) ) +) ” ‘开始位置
js=“(“+Str(k+xy(1) -1) +” “+Str(xy(4) ) +”) ” ‘结束位置
Label 3.Caption=“最大子矩阵和为:”+Str(Sum)
Label 4.Caption=“子矩阵中的元素个数为:”+Str(length*(xy(4) -xy(2) +1) )
Label 5.Caption=“子矩阵位置为:”+ks+“,”+js
End Sub
① ② ③