傳回一個整數數組中最大子數組的和4

題目:傳回一個二維整數數組中最大子數組的和。

要求：

1 輸入一個二維整形數組，數組裡有正數也有負數。

2 二維數組首尾相接，象個一條首尾相接帶子一樣。

3 數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。

4 求所有子數組的和的最大值。要求時間複雜度為O(n)。

設計思想

   目前的解決方案是最笨的方法，窮舉，是以時間複雜度達不到題目的要求，還需要進一步的尋找答案

源代碼

#include<iostream>
#include<time.h>
#include<conio.h>
#include<fstream>
using namespace std;
ofstream out;
void RandIn(int RowIntNum,int ColIntNum,int A[][100])//随機生成一個二維數組
{
    for(int i=0;i<RowIntNum;i++)
    {
        for(int j=0;j<ColIntNum;j++)
        {
            A[i][j]=-(int)rand()%201+100;
            cout<<A[i][j]<<'\t';
        }
        cout<<endl;
    }
}
int MaxArray(int array[],int Maxsize,int &Location)
{
    int max=array[0];//生成最大數值
    Location=0;//最大數值下标位置初始化
    for(int i=0;i<Maxsize;i++)
    {
        if(max<array[i])
        {
            max=array[i];
            Location=i;
        }
    }
    return max;
}
void DivANum(int A[][100],int RowIntNum,int ColIntNum,int SubRowNum,int SubColNum,int EveTSum[],int &Location,int Times)
{
    int sum[10000];//記錄子矩陣的和
    int ArrayNum=0;//生成子矩陣的數目
    int count=0;//子矩陣累加次數
    for(int row=0;row<RowIntNum-SubRowNum+1;row++)
    {
        for(int col=0;col<ColIntNum;col++)//求所有子矩陣
        {
            sum[ArrayNum]=0;
            for(int p=row;p<row+SubRowNum;p++)//求得子矩陣的和
            {
                for(int q=col;q<col+SubColNum;q++)
                {
                    sum[ArrayNum]+=A[p][q%ColIntNum];
                }
            }
            ArrayNum++;//記錄生成的子矩陣數
        }
    }
    EveTSum[Times]=MaxArray(sum,ArrayNum,Location);//記錄每次生成的子矩陣中的最大子矩陣數值
}
void Print(int row,int col, int array[][100])
{
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            out<<array[i][j]<<',';
        }
        out<<'\n';
    }
}
void main()
{
    out.open("text.txt");
    srand((unsigned)time(NULL));
    int Location[100];//記錄每次最大子數組的位置
    int A[100][100],RowIntNum,ColIntNum;
    int SubRowNum,SubColNum;
    int max=0,LocTimes=0;
    int EveTSum[10000];
    int q=0;
    while(q==0)
    {
        cout<<"請輸入行數:";
        cin>>RowIntNum;
        out<<RowIntNum<<',';
        cout<<"請輸入列數:";
        cin>>ColIntNum;
        out<<ColIntNum<<','<<'\n';
        cout<<"整數内容"<<endl;
        RandIn(RowIntNum,ColIntNum,A);//随機生成RowIntNum行,ColIntNum列的數組
        Print(RowIntNum,ColIntNum,A);
        for(SubRowNum=1;SubRowNum<=RowIntNum;SubRowNum++)
        {
            for(SubColNum=1;SubColNum<=ColIntNum;SubColNum++)
            {
                DivANum(A,RowIntNum,ColIntNum,SubRowNum,SubColNum,EveTSum,Location[(SubRowNum-1)*RowIntNum+SubColNum-1],(SubRowNum-1)*RowIntNum+SubColNum-1);
            }
        }
        cout<<"輸出最大矩陣的和"<<endl;
        max=MaxArray(EveTSum,(SubRowNum-1)*(SubColNum-1),LocTimes);
        cout<<max<<endl;
        out<<max;
        out.close();
        cout<<"是否繼續測試(輸入0繼續)"<<endl;
        cin>>q;
        system("cls");
    }
}      

程式截圖

實驗總結

此次試驗的收獲就是熟悉了%和for循環語句的配合對于數組問題産生的效果，對于達到時間複雜度達到o(n),想出的方法大多都無法達到要求，隻能再查找資料找尋新的思路了，之後會貼在下面。