TheAlgorithms/src/test/java/com/thealgorithms/matrix/Kadane2DTest.java at f3a5e039d95e35963f9493e9d99162f26e3e255e · Adarshsingh99/TheAlgorithms · GitHub

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package com.thealgorithms.matrix;


import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

/**
 * Test cases for Kadane2D algorithm
 */
class Kadane2DTest {

    @Test
    void testBasicMatrix() {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        assertEquals(29, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testAllPositive() {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        // Sum of all elements
        assertEquals(45, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testAllNegative() {
        int[][] matrix = {
            {-1, -2, -3},
            {-4, -5, -6},
            {-7, -8, -9}
        };

        // Maximum single element (least negative)
        assertEquals(-1, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testSingleElement() {
        int[][] matrix = {{5}};
        assertEquals(5, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testSingleRow() {
        int[][] matrix = {{-2, 1, -3, 4, -1, 2, 1, -5, 4}};
        assertEquals(6, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testSingleColumn() {
        int[][] matrix = {{-2}, {1}, {-3}, {4}, {-1}, {2}, {1}, {-5}, {4}};
        assertEquals(6, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testMixedValues() {
        int[][] matrix = {
            {2, 1, -3, -4},
            {-5, -1, 4, 0},
            {1, 2, 3, -2}
        };

        assertEquals(9, Kadane2D.maxSumRectangle(matrix));
    }

    @Test
    void testWithCoordinates() {
        int[][] matrix = {
            {1, 2, -1, -4, -20},
            {-8, -3, 4, 2, 1},
            {3, 8, 10, 1, 3},
            {-4, -1, 1, 7, -6}
        };

        Kadane2D.Result result = Kadane2D.maxSumRectangleWithCoordinates(matrix);
        assertEquals(29, result.maxSum);
        assertEquals(1, result.topRow);
        assertEquals(1, result.leftCol);
        assertEquals(2, result.bottomRow);
        assertEquals(3, result.rightCol);
    }

    @Test
    void testNullMatrix() {
        assertThrows(IllegalArgumentException.class, () -> {
            Kadane2D.maxSumRectangle(null);
        });
    }

    @Test
    void testEmptyMatrix() {
        assertThrows(IllegalArgumentException.class, () -> {
            Kadane2D.maxSumRectangle(new int[0][0]);
        });
    }

    @Test
    void testZeroMatrix() {
        int[][] matrix = {
            {0, 0, 0},
            {0, 0, 0},
            {0, 0, 0}
        };

        assertEquals(0, Kadane2D.maxSumRectangle(matrix));
    }
}