1. 給定一個m*n的數組（m,n>=2,數組值>=0），要求選出和最大的子2*2數組。例如：

1 2 3

4 5 6

7 8 9

顯然和最大的2*2子數組是5 6;8 9.下面完成這個功能。

Input: （m*n的數組）

? ? ? ? ? ? 1 2 3 ; 4 5 6 ; 7 8 9

Output: (最大的和)

? ? ? ? ? ? ? 28

解析：這個問題我覺得有兩個難點，第一個就是二維數組的生成，初始時刻給了我們一行字符串，格式如上。我們需要從中讀取二維數組,第二個就是核心算法，這里我們使用暴力解法，兩行兩列地逐步向后向下推進，直到找到最大的和。

代碼：?

#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;vector<string> split( string str,  string pattern)//分割字符串，分隔符是pattern
{vector<string> result;str += pattern;//擴張字符串以方便操作string::size_type pos;int n = str.size();for (int i = 0; i < n;i++){pos = str.find(pattern, i);if (pos<n){string s = str.substr(i, pos - i );result.push_back(s);i = pos +pattern.size()- 1;}}return result;}
int main()
{//讀取二維數組string str;getline(cin, str);vector<string> vecstr = split(str, ";");//第一次分割int m = vecstr.size();//m行int n;//列數vector<vector<int> > arr(m);for (int i = 0; i < m;i++){vector<string> vecstr2 = split(vecstr[i]," ");n = vecstr2.size();arr[i].reserve(n);for (int j = 0; j < n; j++){arr[i].push_back(atoi(vecstr2[j].c_str()));}}//找到最大的和int maxsum = 0;int row , column ;for (int i = 0; i < m - 1; i++)for (int j = 0; j < n - 1; j++){int sum = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1];if (maxsum < sum){row = i;column = j;maxsum = sum;}}cout << "最大的子數組是:" << endl;cout << arr[row][column] << "\t" << arr[row][column + 1] << endl;cout << arr[row + 1][column] << "\t" << arr[row + 1][column + 1] << endl;cout << "最大的和是" << maxsum << endl;}

結果：
1 2 3;4 5 6;7 8 9
最大的子數組是:
5 ? ? ? 6
8 ? ? ? 9
最大的和是28
請按任意鍵繼續. . .

2.已知有一個數組，有正數、負數、0，要求輸出和為0的最長連續子數組。

Input: -1 0 1 2 -1 -2 3 4 -4?

Output:?0 1 2 -1 -2?

解析：

? ? ? ? ? 定義i,j，讓i從前往后遍歷，在i確定的時候,讓j從后往前遍歷，直到遇到第一個為0的時候停下來，計算i,j之間的距離，然后i繼續遍歷，選最長的即可。同時為了節約時間，一旦有一種情形的長度超過整體長度的一半，則i只需遍歷到整體的前一半即可。

代碼：

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <sstream>
#include <numeric>
using namespace std;
typedef vector<int> vecint;
vecint max_subarray(string str)
{stringstream s(str);vecint data,subdata;data.reserve(str.length());int t;while (s>>t){data.push_back(t);}int n = data.size();int disnum = 0;int low=-1, high=-1;for (int i = 0; i < n;i++){if (i >= n / 2 && disnum >= n / 2){break;}int sum = accumulate(data.begin() + i, data.end(), 0);int j = n - 1;while (sum!=0&&j>=i){sum -= data[j--];}if (sum == 0 && (disnum<(j - i + 1))){disnum =j - i + 1;//子數組的長度low = i;high = j;}}if (disnum!=0){for (int k = low; k <= high; k++){subdata.push_back(data[k]);}}return subdata;}int main()
{string str;getline(cin, str);vecint subarray = max_subarray(str);if (subarray.empty()){cout << "there's not such subarray that sum equals to zero" << endl;}else{cout << "Result has founded:" << endl;copy(subarray.begin(), subarray.end(), ostream_iterator<int>(cout, " "));}
}

結果：

-1 0 1 2 -1 -2 3 4 -4
Result has founded:
0 1 2 -1 -2 請按任意鍵繼續. . .