fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. /*
  5. При считывании каждого нового числа сразу же строю матрицы частичных сумм, в i-й ячейке которой хранится сумма первых i элементов исходной матрицы. Этот код работает.
  6.  
  7. Далее начинаю определять максимальную сумму из всех возможных подматриц. Пусть максимальная подматрица нам уже известна. Тогда мы знаем номер ее левого (left) и правого (right) столбцов. Будем искать сумму элементов матрицы с границами left и right.
  8.  
  9. Если left = right = 0, случай тривиальный. Эта матрица - первый столбец, в нем легко найти сумму элементов.
  10.  
  11. Если left != right, то матрица нетривиальна. Фиксируем левый столбец и двигаем правый столбец вправо. В матрице с такими границами находим сумму элементов. Если left = 0, все просто. Сумма матрицы равна сумме элементов столбца с индексом right. Если left != 0, то мы посчитали сумму лишних элементов. Они располагаются левее столбца left. Вычтем из из сумму.
  12.  
  13. Постоянно проверяем, не нашли ли сумму больше предыдущей.
  14. */
  15.  
  16. int main(){
  17. 	int n, p;
  18. 	int sum = 0, max_sum = 0;
  19. 	std::vector< std::vector<int> > m;
  20.  
  21. 	std::cin.sync_with_stdio(false);
  22. 	std::cin >> n;
  23. 	// Устанавливаем размеры матрицы, которая хранит суммы
  24. 	m.resize(n);
  25. 	for(int i = 0; i < n; i++)
  26. 		m[i].resize(n);
  27.  
  28. 	// Если индексы указывают на первую ячейку строки, то просто копируем в нее введенное число
  29. 	// В противном случае копируем в нее сумму числа из предыдущей ячейки и введенного
  30. 	// Таким образом, i-я ячейка строки хранит сумму первых i чисел
  31. 	for(int i = 0; i < n; i++)
  32. 		for(int j = 0; j < n; j++){
  33. 			std::cin >> p;
  34. 			if(j) m[i][j] = m[i][j - 1] + p;
  35. 			else  m[i][j] = p;
  36. 		}
  37.  
  38. 	for(int left = 0; left < n; left++)	// Фиксируем левый столбец искомой матрицы
  39. 		for(int right = left; right < n; right++){	// Двигаем правый столбец искомой матрицы вправо
  40. 			sum = 0;
  41. 			for(int j = 0; j < n; j++){	// Цикл для суммирования по столбцу
  42. 				if(right == 0)
  43. 					sum += m[j][right];	// Суммируем элементы столбца
  44. 				else
  45. 					sum += m[j][right] - m[j][left - 1];
  46. 				//if(sum < 0) sum = 0;
  47. 				max_sum = std::max(sum, max_sum);
  48. 			}
  49. 		}
  50.  
  51. 	for(int i = 0; i < n; i++){
  52. 		for(int j = 0; j < n; j++)
  53. 			std::cout << m[i][j] << " ";
  54. 		std::cout << std::endl;
  55. 	}
  56.  
  57. 	std::cout << max_sum << std::endl;
  58.  
  59. 	std::cin >> p;
  60. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
stdout
copy 
0 -2 -9 -9 
9 11 5 7 
-4 -3 -7 -6 
-1 7 7 5 
9
https://ideone.com/Ov6040
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!