Двумерный массив. Найти подмассив, имеющий наибольшую сумму элементов

@ridikyu · Регистрация: 24.10.2013

Author24 — интернет-сервис помощи студентам

Задан двумерный массив целых чисел. Найдите подмассив, имеющий наибольшую сумму элементов. Например, для приведенного массива, это подмассив:
9 2
-4 1
-1 8
Он имеет сумму 15.

Входные данные: Положительное число N (не более 10) - размерность двумерного массива. Затем N строк по N элементов массива. Элементы не превышают 1000 по своему абсолютному значению.

Выходные данные: Вывести одно число - максимально возможную сумму подмассива.

Пример входных данных
4
0 –2 -7 0
9 2 -6 2
-4 1 -4 1
–1 8 0 –2

Пример выходных данных
15

C++

#include <iostream>
 
int mas[1000][1000];
int masu[1000];
int S;
int main()
{
    int i, j;
    int n;
    
    std::cin >> n;
    {for (i = 0; i < n; ++i)
        for (j = 0 + 1; j < 3 + 1; ++j)
            std::cin >> mas[i][j];
    
    }
 
        {for (i = 0; i < n; ++i)
            for (j = 0 + 1; j < n + 1; ++j)
                S += (mas[i][j]);
        }
    std::cout << S;
    return 0;
}

вот такая вот прога. пока не проверил, ее на пример входных данных, думал что понял что надо делать.
я нахожу сумму всех элементов массива. Помогите решить)))

@_Ivana · 30.11.2014, 04:23

Пожалуйста. Но чтобы не потокать вашей жажде халявы - вот в таком виде:

Haskell

res m = maximum $ map sumrect rects where
    n = length m - 1
    rc = [(r,c)|r<-[0..n],c<-[0..n]]
    rects = concat $ map (\(r0,c0) -> [(r0,c0,r,c)|r<-[r0..n],c<-[c0..n]]) rc
    sumrect (r0,c0,r,c) = ms!!r0!!c0 - ms!!(r+1)!!c0 - ms!!r0!!(c+1) + ms!!(r+1)!!(c+1)
    ms = (map (++[0]).chunksOf (n+1).map sufsum) rc ++ [replicate (n+2) 0]
    sufsum (r,c) = sum.map (sum.drop c) $ drop r m
 
main = print $ res [[0,-2,-7,0],[9,2,-6,2],[-4,1,-4,1],[-1,8,0,-2]]

@ridikyu · 30.11.2014, 09:59 **[ТС]**

_Ivana, спасибо)))

Добавлено через 3 минуты
_Ivana, я само задание понять не могу. что это за подмаслив такой?
0 –2 -7 0
9 2 -6 2
-4 1 -4 1
–1 8 0 –2
как получилось 15 ?

@SlavaSSU · 30.11.2014, 10:07

ridikyu, надо найти в матрице подматрицу с макс суммой чисел в ней. в данном случае это будет подматрица начинающаяся в (2, 1) и заканчивающаяся в элементе (4, 2)

@_Ivana · 30.11.2014, 16:22

ridikyu, потренируйтесь на ~~кошках~~ одномерном массиве, придумайте (найдите/прочитайте) и реализуйте алгоритм поиска в нем подмассива с максимальной суммой элементов. А после небольшим усовершенствованием алгоритм обобщается на двумерный, трехмерный и т.д. случаи.

@ridikyu · 30.11.2014, 16:30 **[ТС]**

_Ivana, ок, только я никак не пойму что это за подмаслив такой. Из чего он состоять должен

Добавлено через 4 минуты
_Ivana, у меня еще задачка, вроде все норм, но почему то ни как не зачтется. Программа, декодирующая закодированную Васей строку

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	30.11.2014, 09:59 [ТС]	3
	_Ivana, спасибо))) Добавлено через 3 минуты _Ivana, я само задание понять не могу. что это за подмаслив такой? 0 –2 -7 0 9 2 -6 2 -4 1 -4 1 –1 8 0 –2 как получилось 15 ? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	30.11.2014, 10:07	4
	ridikyu, надо найти в матрице подматрицу с макс суммой чисел в ней. в данном случае это будет подматрица начинающаяся в (2, 1) и заканчивающаяся в элементе (4, 2) 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	30.11.2014, 16:22	5
	ridikyu, потренируйтесь на ~~кошках~~ одномерном массиве, придумайте (найдите/прочитайте) и реализуйте алгоритм поиска в нем подмассива с максимальной суммой элементов. А после небольшим усовершенствованием алгоритм обобщается на двумерный, трехмерный и т.д. случаи. 0

@ridikyu 0 / 0 / 1 Регистрация: 24.10.2013 Сообщений: 88
	30.11.2014, 16:30 [ТС]	6
	_Ivana, ок, только я никак не пойму что это за подмаслив такой. Из чего он состоять должен Добавлено через 4 минуты _Ivana, у меня еще задачка, вроде все норм, но почему то ни как не зачтется. Программа, декодирующая закодированную Васей строку 0