Dada uma matriz de N linhas e M colunas consiste em três valores {r g b}. A tarefa é encontrar a área do maior triângulo que tem um lado paralelo ao eixo y, ou seja, vertical e a cor dos três vértices é diferente.
Exemplos:  
 

    Input :      N = 4 M =5   
  mat[][] =   
  {   
  r r r r r   
  r r r r g   
  r r r r r   
  b b b b b   
  }   
    Output :     10   
 The maximum area of triangle is 10.   
 Triangle coordinates are (00) containing r (14) containing g (30) containing b.  
   
  
    
 Sabemos que a área de um triângulo = 1/2 * base *altura, então precisamos maximizar a base e a altura do triângulo. Como um lado é paralelo ao eixo y, podemos considerar esse lado como a base do triângulo.   
 Para maximizar a base podemos encontrar a primeira e a última ocorrência de {r g b} para cada coluna. Portanto, temos dois conjuntos de 3 valores para cada coluna. Para base em qualquer coluna, um vértice é do primeiro conjunto e o segundo vértice do segundo conjunto, de modo que tenham valores diferentes.   
 Para maximizar a altura de qualquer coluna como base, o terceiro vértice deve ser escolhido de forma que o vértice esteja mais distante da coluna no lado esquerdo ou direito da coluna com um valor diferente dos outros dois vértices.    
 Agora, para cada coluna, encontre a área máxima do triângulo.   
 Abaixo está a implementação desta abordagem:   
    
 

 C++   
   // C++ program to find maximum area of triangle   // having different vertex color in a matrix.   #include       using     namespace     std  ;   #define R 4   #define C 5   // return the color value so that their corresponding   // index can be access.   int     mapcolor  (  char     c  )   {      if     (  c     ==     'r'  )      return     0  ;      else     if     (  c     ==     'g'  )      return     1  ;      else     if     (  c     ==     'b'  )      return     2  ;   }   // Returns the maximum area of triangle from all   // the possible triangles   double     findarea  (  char     mat  [  R  ][  C  ]     int     r       int     c        int     top  [  3  ][  C  ]     int     bottom  [  3  ][  C  ]      int     left  [  3  ]     int     right  [  3  ])   {      double     ans     =     (  double  )  1  ;      // for each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )      // for each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )      // for each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )      {      // finding the third color of      // vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     INT_MAX     &&      bottom  [  y  ][  i  ]     !=     INT_MIN     &&     left  [  z  ]     !=     INT_MAX  )      {      ans     =     max  (  ans       ((  double  )  1  /  (  double  )  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *      (  i     -     left  [  z  ]));      }      // finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     INT_MAX     &&      bottom  [  y  ][  i  ]     !=     INT_MIN     &&      right  [  z  ]     !=     INT_MIN  )      {      ans     =     max  (  ans       ((  double  )  1  /  (  double  )  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *      (  right  [  z  ]     -     i  ));      }      }      return     ans  ;   }   // Precompute the vertices of top bottom left   // and right and then computing the maximum area.   double     maxarea  (  char     mat  [  R  ][  C  ]     int     r       int     c  )   {      int     left  [  3  ]     right  [  3  ];      int     top  [  3  ][  C  ]     bottom  [  3  ][  C  ];      memset  (  left       INT_MAX       sizeof     left  );      memset  (  right       INT_MIN       sizeof     right  );      memset  (  top       INT_MAX       sizeof     top  );      memset  (  bottom       INT_MIN       sizeof     bottom  );      // finding the r b g cells for the left      // and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )      {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )      {      left  [  mapcolor  (  mat  [  i  ][  j  ])]     =      min  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]     j  );      right  [  mapcolor  (  mat  [  i  ][  j  ])]     =      max  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]     j  );      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )      {      for  (     int     i     =     0  ;     i      <     r  ;     i  ++  )      {      top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     =      min  (  top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     i  );      bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     =      max  (  bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]     i  );      }      }      return     findarea  (  mat       R       C       top       bottom       left       right  );   }   // Driven Program   int     main  ()   {      char     mat  [  R  ][  C  ]     =      {      'r'       'r'       'r'       'r'       'r'        'r'       'r'       'r'       'r'       'g'        'r'       'r'       'r'       'r'       'r'        'b'       'b'       'b'       'b'       'b'        };      cout      < <     maxarea  (  mat       R       C  )      < <     endl  ;      return     0  ;   }   
  Java   
   import     java.util.Arrays  ;   public     class   Main     {      static     int     R     =     4  ;      static     int     C     =     5  ;      static     char  [][]     mat     =     {      {  'r'       'r'       'r'       'r'       'r'  }      {  'r'       'r'       'r'       'r'       'g'  }      {  'r'       'r'       'r'       'r'       'r'  }      {  'b'       'b'       'b'       'b'       'b'  }      };      public     static     void     main  (  String  []     args  )     {      System  .  out  .  println  (  maxArea  (  mat       R       C  ));      }      // Returns the color value so that their corresponding index can be accessed.      static     int     mapColor  (  char     c  )     {      if     (  c     ==     'r'  )     return     0  ;      else     if     (  c     ==     'g'  )     return     1  ;      else     if     (  c     ==     'b'  )     return     2  ;      else     return     -  1  ;      }      // Returns the maximum area of triangle from all the possible triangles      static     double     findArea  (  char  [][]     mat       int     r       int     c       int  [][]     top       int  [][]     bottom       int  []     left       int  []     right  )     {      double     ans     =     10  ;      // For each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )     {      // For each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )     {      // For each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )     {      // Finding the third color of vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // Finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Integer  .  MAX_VALUE     &&      bottom  [  y  ][  i  ]     !=     Integer  .  MIN_VALUE     &&      left  [  z  ]     !=     Integer  .  MAX_VALUE  )     {      ans     =     Math  .  max  (  ans       0.5     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ]  )     *     (  i     -     left  [  z  ]  ));      }      // Finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Integer  .  MAX_VALUE     &&      bottom  [  y  ][  i  ]     !=     Integer  .  MIN_VALUE     &&      right  [  z  ]     !=     Integer  .  MIN_VALUE  )     {      ans     =     Math  .  max  (  ans       0.5     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ]  )     *     (  right  [  z  ]     -     i  ));      }      }      }      }      return     ans  ;      }      // Precompute the vertices of top bottom left and right and then computing the maximum area.      static     double     maxArea  (  char  [][]     mat       int     r       int     c  )     {      int  []     left     =     new     int  [  3  ]  ;      Arrays  .  fill  (  left       Integer  .  MAX_VALUE  );      int  []     right     =     new     int  [  3  ]  ;      Arrays  .  fill  (  right       Integer  .  MIN_VALUE  );      int  [][]     top     =     new     int  [  3  ][  c  ]  ;      for     (  int  []     row     :     top  )     Arrays  .  fill  (  row       Integer  .  MAX_VALUE  );      int  [][]     bottom     =     new     int  [  3  ][  c  ]  ;      for     (  int  []     row     :     bottom  )     Arrays  .  fill  (  row       Integer  .  MIN_VALUE  );      // Finding the r b g cells for the left and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      int     color     =     mapColor  (  mat  [  i  ][  j  ]  );      left  [  color  ]     =     Math  .  min  (  left  [  color  ]       j  );      right  [  color  ]     =     Math  .  max  (  right  [  color  ]       j  );      }      }      // Finding set of {r g b} of top and bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      int     color     =     mapColor  (  mat  [  i  ][  j  ]  );      top  [  color  ][  j  ]     =     Math  .  min  (  top  [  color  ][  j  ]       i  );      bottom  [  color  ][  j  ]     =     Math  .  max  (  bottom  [  color  ][  j  ]       i  );      }      }      return     findArea  (  mat       r       c       top       bottom       left       right  );      }   }   
  Python3   
   # Python3 program to find the maximum    # area of triangle having different    # vertex color in a matrix.    # Return the color value so that their    # corresponding index can be access.    def   mapcolor  (  c  ):   if   c   ==   'r'  :   return   0   elif   c   ==   'g'  :   return   1   elif   c   ==   'b'  :   return   2   # Returns the maximum area of triangle    # from all the possible triangles    def   findarea  (  mat     r     c     top     bottom     left     right  ):   ans   =   1   # for each column    for   i   in   range  (  0     c  ):   # for each top vertex    for   x   in   range  (  0     3  ):   # for each bottom vertex    for   y   in   range  (  0     3  ):   # finding the third color of    # vertex either on right or left.    z   =   3   -   x   -   y   # finding area of triangle on    # left side of column.    if   (  x   !=   y   and   top  [  x  ][  i  ]   !=   INT_MAX   and   bottom  [  y  ][  i  ]   !=   INT_MIN   and   left  [  z  ]   !=   INT_MAX  ):   ans   =   max  (  ans     0.5   *   (  bottom  [  y  ][  i  ]   -   top  [  x  ][  i  ])   *   (  i   -   left  [  z  ]))   # finding area of triangle on right side of column.    if   (  x   !=   y   and   top  [  x  ][  i  ]   !=   INT_MAX   and   bottom  [  y  ][  i  ]   !=   INT_MIN   and   right  [  z  ]   !=   INT_MIN  ):   ans   =   max  (  ans     0.5   *   (  bottom  [  y  ][  i  ]   -   top  [  x  ][  i  ])   *   (  right  [  z  ]   -   i  ))   return   ans   # Precompute the vertices of top bottom left    # and right and then computing the maximum area.    def   maxarea  (  mat     r     c  ):   left   =   [  -  1  ]   *   3   right   =   [  0  ]   *   3   top   =   [[  -  1   for   i   in   range  (  C  )]   for   j   in   range  (  3  )]   bottom   =   [[  0   for   i   in   range  (  C  )]   for   j   in   range  (  3  )]   # finding the r b g cells for    # the left and right vertices.    for   i   in   range  (  0     r  ):   for   j   in   range  (  0     c  ):   left  [  mapcolor  (  mat  [  i  ][  j  ])]   =    min  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]   j  )   right  [  mapcolor  (  mat  [  i  ][  j  ])]   =    max  (  left  [  mapcolor  (  mat  [  i  ][  j  ])]   j  )   # finding set of r g b of top    # and bottom for each column.    for   j   in   range  (  0     c  ):   for   i   in   range  (  0     r  ):   top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   =    min  (  top  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   i  )   bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   =    max  (  bottom  [  mapcolor  (  mat  [  i  ][  j  ])][  j  ]   i  )   return   int  (  findarea  (  mat     R     C     top     bottom     left     right  ))   # Driver Code   if   __name__   ==   '__main__'  :   R     C   =   4     5   mat   =   [[  'r'     'r'     'r'     'r'     'r'  ]   [  'r'     'r'     'r'     'r'     'g'  ]   [  'r'     'r'     'r'     'r'     'r'  ]   [  'b'     'b'     'b'     'b'     'b'  ]]   INT_MAX     INT_MIN   =   float  (  'inf'  )   float  (  '-inf'  )   print  (  maxarea  (  mat     R     C  ))   # This code is contributed by Rituraj Jain   
  C#   
   // C# program to find maximum area of triangle   // having different vertex color in a matrix.   using     System  ;   class     MainClass     {      const     int     R     =     4  ;      const     int     C     =     5  ;      // return the color value so that their corresponding      // index can be access.      static     int     mapcolor  (  char     c  )      {      if     (  c     ==     'r'  )     {      return     0  ;      }      else     if     (  c     ==     'g'  )     {      return     1  ;      }      else     if     (  c     ==     'b'  )     {      return     2  ;      }      else     {      return     -  1  ;      }      }      // Returns the maximum area of triangle from all      // the possible triangles      static     double     findarea  (  char  [     ]     mat       int     r       int     c        int  [     ]     top       int  [     ]     bottom        int  []     left       int  []     right  )      {      double     ans     =     .  0  ;      // for each column      for     (  int     i     =     0  ;     i      <     c  ;     i  ++  )     {      // for each top vertex      for     (  int     x     =     0  ;     x      <     3  ;     x  ++  )     {      // for each bottom vertex      for     (  int     y     =     0  ;     y      <     3  ;     y  ++  )     {      // finding the third color of      // vertex either on right or left.      int     z     =     3     -     x     -     y  ;      // finding area of triangle on left side      // of column.      if     (  x     !=     y      &&     top  [  x       i  ]      !=     int  .  MaxValue  &&      bottom  [  y       i  ]      !=     int  .  MinValue  &&     left  [  z  ]      !=     int  .  MaxValue  )     {      ans     =     Math  .  Max  (      ans        (  1.0     /     2.0  )      *     (  bottom  [  y       i  ]     -     top  [  x       i  ])      *     (  i     -     left  [  z  ]));      }      // finding area of triangle on right      // side of column.      if     (  x     !=     y      &&     top  [  x       i  ]      !=     int  .  MaxValue  &&      bottom  [  y       i  ]      !=     int  .  MinValue  &&     right  [  z  ]      !=     int  .  MinValue  )     {      ans     =     Math  .  Max  (      ans        (  1.0     /     2.0  )      *     (  bottom  [  y       i  ]     -     top  [  x       i  ])      *     (  right  [  z  ]     -     i  )  +  4  );      }      }      }      }      return     ans  ;      }      // Precompute the vertices of top bottom left      // and right and then computing the maximum area.      static     double     maxarea  (  char  [     ]     mat       int     r       int     c  )      {      int  []     left      =     {     int  .  MaxValue       int  .  MaxValue       int  .  MaxValue     };      int  []     right      =     {     int  .  MinValue       int  .  MinValue       int  .  MinValue     };      int  [     ]     top     =     new     int  [  3       C  ];      int  [     ]     bottom     =     new     int  [  3       C  ];      // finding the r b g cells for the left      // and right vertices.      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      int     color     =     mapcolor  (  mat  [  i       j  ]);      if     (  color     !=     -  1  )     {      left  [  color  ]     =     Math  .  Min  (  left  [  color  ]     j  );      right  [  color  ]      =     Math  .  Max  (  right  [  color  ]     j  );      }      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  int     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  int     i     =     0  ;     i      <     r  ;     i  ++  )     {      int     color     =     mapcolor  (  mat  [  i       j  ]);      if     (  color     !=     -  1  )     {      top  [  color       j  ]      =     Math  .  Min  (  top  [  color       j  ]     i  );      bottom  [  color       j  ]      =     Math  .  Max  (  bottom  [  color       j  ]     i  );      }      }      }      return     findarea  (  mat       R       C       top       bottom       left        right  );      }      // Driven Program      public     static     void     Main  (  string  []     args  )      {      char  [     ]     mat     =     new     char  [     ]     {      {     'r'       'r'       'r'       'r'       'r'     }      {     'r'       'r'       'r'       'r'       'g'     }      {     'r'       'r'       'r'       'r'       'r'     }      {     'b'       'b'       'b'       'b'       'b'     }      };      Console  .  WriteLine  (  maxarea  (  mat       R       C  ));      }   }   
  JavaScript   
   // Javascript program to find maximum area of triangle   // having different vertex color in a matrix.   // return the color value so that their corresponding   // index can be accessed.   function     mapcolor  (  c  )     {      if     (  c     ==     'r'  )     return     0  ;      else     if     (  c     ==     'g'  )     return     1  ;      else     if     (  c     ==     'b'  )     return     2  ;   }   // Returns the maximum area of triangle from all   // the possible triangles   function     findarea  (  mat       r       c       top       bottom       left       right  )     {      let     ans     =     10  ;      // for each column      for     (  let     i     =     0  ;     i      <     c  ;     i  ++  )     {      // for each top vertex      for     (  let     x     =     0  ;     x      <     3  ;     x  ++  )     {      // for each bottom vertex      for     (  let     y     =     0  ;     y      <     3  ;     y  ++  )     {      // finding the third color of      // vertex either on right or left.      let     z     =     3     -     x     -     y  ;      // finding area of triangle on left side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Number  .  MAX_SAFE_INTEGER     &&      bottom  [  y  ][  i  ]     !=     Number  .  MIN_SAFE_INTEGER     &&      left  [  z  ]     !=     Number  .  MAX_SAFE_INTEGER  )     {      ans     =     Math  .  max  (  ans       (  1  /  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *     (  i     -     left  [  z  ]));      }      // finding area of triangle on right side of column.      if     (  x     !=     y     &&     top  [  x  ][  i  ]     !=     Number  .  MAX_SAFE_INTEGER     &&      bottom  [  y  ][  i  ]     !=     Number  .  MIN_SAFE_INTEGER     &&      right  [  z  ]     !=     Number  .  MIN_SAFE_INTEGER  )     {      ans     =     Math  .  max  (  ans       (  1  /  2  )     *      (  bottom  [  y  ][  i  ]     -     top  [  x  ][  i  ])     *     (  right  [  z  ]     -     i  ));      }      }      }      }      return     ans  ;   }   // Precompute the vertices of top bottom left   // and right and then computing the maximum area.   function     maxarea  (  mat       r       c  )     {      let     left     =     [  Number  .  MAX_SAFE_INTEGER       Number  .  MAX_SAFE_INTEGER       Number  .  MAX_SAFE_INTEGER  ];      let     right     =     [  Number  .  MIN_SAFE_INTEGER       Number  .  MIN_SAFE_INTEGER       Number  .  MIN_SAFE_INTEGER  ];      let     top     =     Array  .  from  ({  length  :     3  }     ()     =>     Array  (  c  ).  fill  (  Number  .  MAX_SAFE_INTEGER  ));      let     bottom     =     Array  .  from  ({  length  :     3  }     ()     =>     Array  (  c  ).  fill  (  Number  .  MIN_SAFE_INTEGER  ));      // finding the r b g cells for the left      // and right vertices.      for     (  let     i     =     0  ;     i      <     r  ;     i  ++  )     {      for     (  let     j     =     0  ;     j      <     c  ;     j  ++  )     {      let     color     =     mapcolor  (  mat  [  i  ][  j  ]);      left  [  color  ]     =     Math  .  min  (  left  [  color  ]     j  );      right  [  color  ]     =     Math  .  max  (  right  [  color  ]     j  );      }      }      // finding set of {r g b} of top and      // bottom for each column.      for     (  let     j     =     0  ;     j      <     c  ;     j  ++  )     {      for     (  let     i     =     0  ;     i      <     r  ;     i  ++  )     {      let     color     =     mapcolor  (  mat  [  i  ][  j  ]);      top  [  color  ][  j  ]     =     Math  .  min  (  top  [  color  ][  j  ]     i  );      bottom  [  color  ][  j  ]     =     Math  .  max  (  bottom  [  color  ][  j  ]     i  );      }      }      return     findarea  (  mat       r       c       top       bottom       left       right  );   }   // Driven Program   const     R     =     4  ;   const     C     =     5  ;   const     mat     =     [      [  'r'       'r'       'r'       'r'       'r'  ]      [  'r'       'r'       'r'       'r'       'g'  ]      [  'r'       'r'       'r'       'r'       'r'  ]      [  'b'       'b'       'b'       'b'       'b'  ]   ];   console  .  log  (  maxarea  (  mat       R       C  ));   // akashish__   
   
    Saída:       
  
 10  
  
    Complexidade de tempo:    OU(R*C)   
    Espaço Auxiliar:    O(R + C)    
    Fonte:         https://stackoverflow.com/questions/40078660/máxima-área-de-triângulo-tendo-todos-vértices-de-cor-diferente     
    
         Criar questionário