如何將數組分解爲固定大小的小數組？ （在C中）

Question

我試圖在Hacker Rank中做一個練習，但發現我的代碼（下面）太線性了。爲了使它更好，我想知道是否有可能將數組分解爲固定大小的小數組來完成此練習。

The Exersise on HackerRank

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 

int main() { 

int N, M, Y, X; 
scanf("%d %d %d %d", &N, &M, &Y, &X); 

int max = 0; 
int total = 0; 
int data[N][M]; 

for(int i = 0; i < N; i++) 
{ 
    for(int j = 0; j < M; j++) 
    { 
     scanf("%d",&(data[i][j]));  
    } 
} 


for(int i = 0; i < N; i++) 
{ 
    for(int j = 0; j < M; j++) 
    { 
     total = 0; 

      for(int l = 0; (l < Y) && (i + Y) <= N; l++) 
      { 

       for(int k = 0; (k < X) && (j + X <= M); k++) 
       { 
        total += data[i+l][j+k]; 
       } 

       if(total > max) 
        max = total;      
     } 
    } 
} 

printf("%d",max); 
return 0; 
} 

Answer 1

儘管「破」成塊意味着我們會被在內存中移動的東西，你可以去「觀察」這樣的數組，它是等價的。

在一個非常真實的意義上，數組的名稱只是一個指向第一個元素的指針。當您取消引用數組的元素時，將使用數組映射函數來執行指針運算，以便可以找到正確的元素。這是必要的，因爲C數組本身並沒有任何指針信息來識別元素。

然而，如何將數組存儲的本質用於將數據視爲任意大小的任意數組。例如，如果我們有：

int integers[] = {1,2,3,4,5,6,7,8,9,10};

，你可以認爲這是一個數組：

for(i=0;i!=10;i++){ printf("%d\n", integers[i]); }

但上述陣列也可以做到這一點出發：

int *iArray1, *iArray2; 
iArray1 = integers; 
iArray2 = integers + (5 * sizeof(int)); 
for(i=0;i!=5;i++){ printf("%d - %d\n", iArray1[i], iArray2[i]);} 

這樣我們選擇查看數據爲兩個5 t erm數組。

Answer 2

該問題不在線性解決方案中。主要問題在於算法的複雜性。因爲它寫的是O（N^4）。此外，我認爲你的解決方案是不正確的，因爲：

ceulluar塔可以覆蓋Y行X列Regtangular區域。

這並不意味着什麼y行和X列恕我直言，你能找到一個解決方案，其中的尺寸小於X，Y

的問題，例如，使用動態規劃是在合理的時間內可解。嘗試使用動態編程優化您的程序到O（N^2）。