UC知道取最大值 pascal急需
来源：百度知道 编辑：UC知道 时间：2024/06/02 10:51:20
程序名称 maximum.pas/c/cpp
输入文件 maximum.in
输出文件 maximum.out
时间限制 2秒
测试数据 10分*10数据=100分
【问题描述】
今有一两行n列的长矩阵，其中的数有正有负，均不超出整数的范围。小明想从这个长矩阵中圈出一个“凹”字形（可正可倒），使得这个“凹”字形中的所有数之和尽可能大，请问能达到的最大值是多少？
【输入说明】
输入第一行包含一个整数n，即矩阵的列数，n小于1000000。以下两行，每行包含n个数，用来描述这个矩阵。所有数在整数范围内。
【输出说明】
输出包含一行一个数，即求出的最大值。
【输入样例1】maximum.in
4
1 -1 1 1
-4 1 1 1
【输出样例1】maximum.out
3
【输入样例2】
10
47 -10 48 -24 -14 3 -40 -23 10 -25
-1 -28 25 31 -20 -48 -22 49 26 –48
【输出样例2】
116 //蓝色部分
var
num:array[1..2,1..1000000] of longint;
max,n,i,a:longint;
begin
//**************input**************\\
readln(n);
for i:=1 to n do
read(num[1,i]);
readln;
for i:=1 to n do
read(num[2,i]);
max:=-maxlongint;
//**************main***************\\
for i:=1 to n-2 do
begin
a:=num[1,i]+num[2,i]+num[1,i+2]+num[2,i+2];
if num[1,i+1]>num[2,i+1]then a:=a+num[1,i+1] else a:=a+num[2,i+1];
if a>max then max:=a;
end;
//*************output**************\\
writeln(max);
end.
程序就是这样了，但是我觉得你的第二个样例好像有问题
我程序算，人脑算，算来算去也只有109，拜托你把“蓝色部分”标出来好么？
假设矩形的两列分别为a,b:array of longint;
这里只考虑"凹"字形倒过来的情况,另一种情况类似
用sum数组记录a的部分和序列,即sum[i]=a[1]+...+a[i]=sum[i-1]+a[i],且sum[0]=0
那么当"凹"字形的两竖分别在第j列和第i列的时候(1<=j<i<=n),总和为sum[i]-sum[j-1]+b[i]+b[j]=sum[i]+b[i]-(sum[j-1]-b[j])
另开一数组c,令c[i]=sum[i-1]-b[i]
那么&quo