FilesExpand file tree

 master

/

sub_rectangular_maximum_sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

86 lines (62 loc) · 2.16 KB

 master

/

sub_rectangular_maximum_sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

86 lines (62 loc) · 2.16 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

"""

Problem Statement

=================

Write a program to find maximum sum rectangle in give 2D matrix. Assume there is at least one positive number in the 2D

matrix.

Solution:

--------

* Keep temp array with size as number of rows. Start left and right from 0 and keep adding values for each row and

maintain them in this temp array.

* Run Kadane's algorithm to find max sum subarray in temp. Now increment right by 1.

* When right reaches last column reset right to 1 and left to 1.

Analysis

--------

* Space complexity of this algorithm is O(row)

* Time complexity of this algorithm is O(row*col*col)

Video

-----

* https://youtu.be/yCQN096CwWM

References

----------

* http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

"""

from collections import namedtuple

Result = namedtuple("Result","maxSum leftBound rightBound upBound lowBound")

KadanesResult = namedtuple("KadanesResult","maxSum start end")

def kadanes(temp):

max = 0

maxStart = -1

maxEnd = -1

currentStart = 0

maxSoFar = 0

for i in range(0, len(temp)):

maxSoFar += temp[i]

if maxSoFar < 0:

maxSoFar = 0

currentStart = i + 1

if maxSoFar > max:

maxStart = currentStart

maxEnd = i

max = maxSoFar

return KadanesResult(max, maxStart, maxEnd)

def max_sub_sub_rectangle(rectangle):

rows = len(rectangle)

cols = len(rectangle[0])

result = Result(float("-inf"), -1, -1, -1, -1)

for left in range(cols):

temp = [0 for _ in range(rows)]

for right in range(left, cols):

for i in range(rows):

temp[i] += rectangle[i][right]

kadanes_result = kadanes(temp)

if kadanes_result.maxSum > result.maxSum:

result = Result(kadanes_result.maxSum, left, right, kadanes_result.start, kadanes_result.end)

return result

if __name__ == '__main__':

rectangle = [[2, 1, -3, -4, 5],

[0, 6, 3, 4, 1],

[2, -2, -1, 4, -5],

[-3, 3, 1, 0, 3]]

result = max_sub_sub_rectangle(rectangle)

assert 18 == result.maxSum

print result