C语言问题 又要麻烦大家了 这道题实在没有思路

一道C语言题目，很难，对我很重要，但是我没有思路，希望大家帮帮我~

多看书、多思考。编程的思维方式也是需要锻炼的

最大子矩阵，最大连续子数组进阶，动态规划初级，poj1050
题目描述：现给出一个N*N矩阵，要求求出拥有最大和的子矩阵的和。
例如：

这样的一个矩阵，最大子矩阵的和为15；
此题可以让人联想到求最大连续子数组，求最大子数组在上一篇文章中http://www.cnblogs.com/tz346125264/p/7560708.html。
分析：最大子矩阵可以看为求最大连续子数组拓展到二维数组上，因为矩阵的性质同样在横向竖向上需要连续，那么可以想办法将这个二维数组简化为求连续子数组。
思考：
1.要求最大子矩阵，必须保证每个矩阵都被浏览到，为了保证运行时间尽可能不要重复浏览同一矩阵，故需制定规则，规则定为用i表示起始行，j表示终止行，j>=i，再使用k对列进行遍历，即可覆盖所有矩阵。
2.进行化简成求连续子数组操作，以上为例，设i=2,j=4那么这个矩阵是这样，那么化为连续子数组即为4（9-4-1），11（2+1+8），-10（-6-4+0），1（2+1-2）
求这个连续数组的最大连续子数组和便是这个矩阵（以i=2作为起始行，j=4作为终止行）的最大子矩阵，如此，整个矩阵的最大子矩阵便是这些最大子矩阵中的最大值。
上代码：

#include#includeusing namespace std;int main(){ int n; int a[101][101]; int temp[101];cin>>n; for(int i=1;i>a[i][j]; /*为什么要进行相加？在化简为求连续最大子数组时，需要将i到j行的数进行相加sum(i,j)，而这个sum{i,j}可有sum{0,j}-sum{0,i}得到为此提前做出相加方便之后化简*/a[i][j]+=a[i-1][j];}} int max = -10000; for(int i=1;i=0){temp[k]=temp[k-1]+a[j][k]-a[i][k];}else{temp[k]=a[j][k]-a[i][k];} if(temp[k]>max){max = temp[k];}}}}cout<<max<<endl; return 0;}

4个人有一个说假话，其他三个说真话。可以这样假设：假如A说的是真话，那么，会有可能的答案；如果A说的是假话的话，相应的也有相应的答案。当然这样的答案里边的人可能不止一个。然后确定4个人每个人说真话和说假话分别对应的嫌疑犯人。然后按顺序假定每个人说的是假话，剩下的是真话，在对应的答案中找有没有公共解。这样就造出了嫌疑犯人
A | B C D | A
B | C | A B D
C | D | A B C
D | A B C | D
可以看出，当C说的是假话的时候，A（B C D）B(C) C(A B C )D(A B C )交集为C
在程序中，可以用适当的数据表示每个人的答案，和根据答案分析出的真话和假话的嫌疑人。然后分别假设每个人说的是假话，然后看有没有公共的解，有的话，就是了.....

循环问题。。。因为只有一个人说假话，可以依次假设A,B,C,D其中一个人说了假话，
然后反判断。当某个假设没有矛盾的时候，没错。。凶手就是他了。。你比柯南还柯南了。

并查集,用来判断逻辑关系,可以上百科查一下,不过建议你先练一下基础的并查集

相关视频