一、 【noip2013】序列重排

全局数组变量 a 定义如下：

const int SIZE=100; 
int a[SIZE],n;

它记录着一个长度为 n 的序列 a[1] ，a[2] ，… ， a[n] 。现在需要一个函数，以整数 p(1 ≤p≤ n) 为参数，

实现如下功能： 将序列 a 的前 p 个数与后 n-p 个数对调， 且不改变这 p 个数（或 n-p 个数）之间的相对位置。

例如，长度为 5 的序列 1， 2，3，4，5，当 p=2 时重排结果为 3，4， 5，1，2。

可以用时间换空间，使用时间复杂度为O(n^2)、空间复杂度为 O(1) 的算法：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=100; 
int a[SIZE],n; 
void swap2(int p){
    int i, j, temp;
    for (i = p + 1;i <= n;i++) {
        temp = a[i];
        for (j = i;j >= (i-p+1) ; j--)
            a[j] = a[j - 1];
        a[i-p] = temp;
    }
}
int main(){
    int  p;
    cin >> n >> p;
    for(int i = 1 ; i <= n; i++){
        cin >> a[i];
    }
    swap2(p);
    for(int i = 1 ;i <= n ; i++){
        cout << a[i] << " ";
    }
    return 0;
}

事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：

void swap3(int p){
    int start1, end1, start2, end2, i, j, temp;
    start1 = 1;
    end1 = p;
    start2 = p + 1;
    end2 = n;
    while (true) {
        i = start1;
        j = start2;
        while ((i <= end1) && (j <= end2)) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j++;
        }
        if (i <= end1)
            start1 = i;
        else if (④) {
            start1 =⑤;
            end1 =⑥;
            start2 = j;
        }else
            break;
    }
}

二、最大子矩阵和

给出 m行 n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。

输入第一行包含两个整数 m和 n，即矩阵的行数和列数。之后 m行，每行 n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。