fork download
copy 
  1. /*******************************************************************
  2. Copyright(c) 2016, Harry He
  3. All rights reserved.
  4.  
  5. Distributed under the BSD license.
  6. (See accompanying file LICENSE.txt at
  7. https://g...content-available-to-author-only...b.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
  8. *******************************************************************/
  9.  
  10. #include <algorithm>
  11. #include <iostream>
  12.  
  13. int getMaxValue_solution1(const int* values, int rows, int cols)
  14. {
  15.     if(values == nullptr || rows <= 0 || cols <= 0)
  16.         return 0;
  17.  
  18.     int** maxValues = new int*[rows];
  19.     for(int i = 0; i < rows; ++i)
  20.         maxValues[i] = new int[cols];
  21.  
  22.     for(int i = 0; i < rows; ++i)
  23.     {
  24.         for(int j = 0; j < cols; ++j)
  25.         {
  26.             int left = 0;
  27.             int up = 0;
  28.  
  29.             if(i > 0)
  30.                 up = maxValues[i - 1][j];
  31.  
  32.             if(j > 0)
  33.                 left = maxValues[i][j - 1];
  34.  
  35.             maxValues[i][j] = std::max(left, up) + values[i * cols + j];
  36.         }
  37.     }
  38.  
  39.     int maxValue = maxValues[rows - 1][cols - 1];
  40.  
  41.     for(int i = 0; i < rows; ++i)
  42.         delete[] maxValues[i];
  43.     delete[] maxValues;
  44.  
  45.     return maxValue;
  46. }
  47.  
  48. int getMaxValue_solution2(const int* values, int rows, int cols)
  49. {
  50.     if(values == nullptr || rows <= 0 || cols <= 0)
  51.         return 0;
  52.  
  53.     int* maxValues = new int[cols];
  54.     for(int i = 0; i < rows; ++i)
  55.     {
  56.         for(int j = 0; j < cols; ++j)
  57.         {
  58.             int left = 0;
  59.             int up = 0;
  60.  
  61.             if(i > 0)
  62.                 up = maxValues[j];
  63.  
  64.             if(j > 0)
  65.                 left = maxValues[j - 1];
  66.  
  67.             maxValues[j] = std::max(left, up) + values[i * cols + j];
  68.         }
  69.     }
  70.  
  71.     int maxValue = maxValues[cols - 1];
  72.  
  73.     delete[] maxValues;
  74.  
  75.     return maxValue;
  76. }
  77.  
  78. // ==============test code================
  79. void test(const char* testName, const int* values, int rows, int cols, int expected)
  80. {
  81.     if(getMaxValue_solution1(values, rows, cols) == expected)
  82.         std::cout << testName << ": solution1 passed." << std::endl;
  83.     else
  84.         std::cout << testName << ": solution1 FAILED." << std::endl;
  85.  
  86.     if(getMaxValue_solution2(values, rows, cols) == expected)
  87.         std::cout << testName << ": solution2 passed." << std::endl;
  88.     else
  89.         std::cout << testName << ": solution2 FAILED." << std::endl;
  90. }
  91.  
  92. void test1()
  93. {
  94.     int values[][4] = {
  95.         { 1, 10, 3, 8 },
  96.         { 12, 2, 9, 6 },
  97.         { 5, 7, 4, 50 },
  98.         { 3, 7, 16, 5 }
  99.     };
  100.     int expected = 85;
  101.     test("test2", (const int*) values, 4, 4, expected);
  102. }
  103.  
  104. int main(int argc, char* argv[])
  105. {
  106.     test1();
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
test2: solution1 passed.
test2: solution2 passed.
https://ideone.com/ga0pp6
language:
C++ (gcc 8.3)
created:
4 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!