CodingInterview/lc_85.cpp at master · ssripadham/CodingInterview · 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
/*
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]


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

dp[i,j] += a[i+1,j]
dp[i,j] += a[i, j+1]

1 1 = 2

1 1
0 1  = 2

0 1
1 0 = 1 (if 0 don't change max)


0 1
1 1  = 2 (if 1 , case 1: atleast one neighbor is 0 : max is max(dp[i-1,j],dp[i][j-1]))
                 case 2: all neighbor is 1 )
1 4
6 0
      1 1
      1 1
0 0 0 1 1     3 6
1 1 1 1 1     4 8

1 1  = 4

1 1 0
1 1 1 = 4

1 1 1
1 1 1 =6
*/
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {

        if (matrix.empty()){
            return 0;
        }

        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(),0));

        dp[0][0] = matrix[0][0]  - '0';
        int maximum = matrix[0][0]-'0';

        for (int i = 1; i < matrix.size(); ++i) {
            dp[i][0] = dp[i-1][0] + (matrix[i][0]-'0');
            maximum = max(maximum, dp[i][0]);
        }

        for (int j = 1; j < matrix[0].size(); ++j) {
            dp[0][j] = dp[0][j-1]+ matrix[0][j]-'0';
            maximum = max(maximum, dp[0][j]);
        }

        for (int i = 2; i < matrix.size(); ++i){
            for (int j = 2; j < matrix[0].size(); ++j){
                if (matrix[i-1][j] -'0' == 1 && matrix[i][j-1] -'0' == 1 && matrix[i-1][j-1] - '0' == 1) {

                    //highest even + 2
                    int max1 = max(dp[i][j-1], dp[i-1][j]);
                    int num1 = (dp[i][j-1]%2 == 0)? dp[i][j-1]: 1;
                    int num2 = (dp[i-1][j]%2 == 0)? dp[i-1][j]: 1;
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                    dp[i][j] = max(dp[i][j],max(num1, num2) + 2);
                    maximum = max(maximum, dp[i][j]);
                } else {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])+ (matrix[i][j] -'0');
                    maximum = max(maximum, dp[i][j]);
                }
            }

        }

        return maximum;

    }
};