二维数组---两个数和的最大值

solution：

　　把二维数组转换为一维数组，那么一维数组的长度为N = ROW  *  COL,

假设二维数组  a[2][3] = { {1, 3, 1}, {2, 4, 5} }; 那么其二维数组为  b[6] = { 1, 3, 1, 2, 4, 5 };

那么存在这样的关系 b[ i ] = a[i  /  COL][i  %  COL], 此时ROW = 2, COL = 3;

比如 b[2] = a[2/3][2%3] = a[0][2] = 1;有了这层关系，就可以做了.

　　对一维数组的b[i]（i = 0,1,2…… ,N - 1）开始，分别与b[0] - b[N - 1]相加，判断是否满足“不同行不同列”的条件，满足就把maxVal求出来，与之前的maxVal做比较,把较大的给maxVal，直到比较结束，

如此就可以求出最大值了，时间复杂度为O(N2)；

 

 

/* 
    problem: 给定一个二维数组，找两个数使其和为最大的，要求这两个数不同行不同列。 
    solution：把二维数组转换为一维数组，那么一维数组的长度为N = ROW * COL, 
    假设二维数组a[2][3] = { {1, 3, 1}, {2, 4, 5} };那么其二维数组为b[6] = { 1, 3, 1, 2, 4, 5 }; 
    那么存在这样的关系b[i] = a[i / COL][i % COL],此时ROW = 2, COL = 3;比如 b[2] = a[2/3][2%3] = a[0][2] = 1; 
    有了这层关系，就可以做了，对一维数组的b[i]（i = 0,1,2…… ,N - 1）开始，分别与b[0] - b[N - 1]相加，判断是否满足 
    “不同行不同列”的条件，满足就把maxVal求出来，与之前的maxVal做比较,把较大的给maxVal，直到比较结束， 
    如此就可以求出最大值了，时间复杂度为O(N2)； 

*/  
  
#include <stdio.h>  
#include <stdlib.h>  
#define ROW 2   //行数  
#define COL 3   //列数  
//typedef double ArrayType;  
int main(void)  
{  
    int a[ROW][COL] = { {1, 3, 1},  
                        {2, 4, 5}};// 给定的二维数组  
    int iterx = 0, itery = 0;// 用于循环计数控制  
    int N = ROW * COL;    //一维数组的长度  
    int maxVal = 0;//存储最大数值  
    int maxsubF = 0 , maxsubS = 0;// F :First number    S: Second number  
    int x = 0, y = 0;  // 保存两个数字的位置  
    for(iterx = 0; iterx < N; iterx++)  
    {  
        for(itery = 0; itery < N; itery++)  
        {  
            maxsubF = a[iterx / COL][iterx % COL];//第一个数F  
            maxsubS = a[itery / COL][itery % COL];//第二个数S  
            //不同行不同列的判读，和最大值的判断  
            if(maxsubF + maxsubS > maxVal && (iterx / COL != itery / COL) && (iterx % COL != itery % COL))  
            {  
                maxVal = maxsubF + maxsubS;  
                x = iterx;  
                y = itery;  
            }  
        }  
    }  
    printf("The MAX sum is %d \n", maxVal);  
    printf("first NUM: a[%d][%d] = %d,  Second NUM: a[%d][%d] = %d\n", x / COL, x % COL , a[x / COL][x % COL], y / COL, y % COL, a[y / COL][y % COL]);  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,