Facebook
From Alperen Kocabalkan, 7 Months ago, written in C#.
Embed
Download Paste or View Raw
Hits: 380
  1. using System;
  2. using System.IO;
  3.  
  4. class Program
  5. {
  6.     static void Main()
  7.     {
  8.         string pyramidStr = @"
  9. 215
  10. 193 124
  11. 117 237 442
  12. 218 935 347 235
  13. 320 804 522 417 345
  14. 229 601 723 835 133 124
  15. 248 202 277 433 207 263 257
  16. 359 464 504 528 516 716 871 182
  17. 461 441 426 656 863 560 380 171 923
  18. 381 348 573 533 447 632 387 176 975 449
  19. 223 711 445 645 245 543 931 532 937 541 444
  20. 330 131 333 928 377 733 017 778 839 168 197 197
  21. 131 171 522 137 217 224 291 413 528 520 227 229 928
  22. 223 626 034 683 839 053 627 310 713 999 629 817 410 121
  23. 924 622 911 233 325 139 721 218 253 223 107 233 230 124 233";
  24.  
  25.         string[] rows = pyramidStr.Trim().Split('\n');
  26.         int[][] pyramid = new int[rows.Length][];
  27.         for (int i = 0; i < rows.Length; i++)
  28.         {
  29.             string[] cols = rows[i].Split(' ');
  30.             pyramid[i] = new int[cols.Length];
  31.             for (int j = 0; j < cols.Length; j++)
  32.             {
  33.                 pyramid[i][j] = int.Parse(cols[j]);
  34.             }
  35.         }
  36.  
  37.         int[][][] path = new int[pyramid.Length][][];
  38.         for (int i = 0; i < pyramid.Length; i++)
  39.         {
  40.             path[i] = new int[pyramid[i].Length][];
  41.         }
  42.  
  43.         for (int i = pyramid.Length - 1; i >= 0; i--)
  44.         {
  45.             for (int j = 0; j < pyramid[i].Length; j++)
  46.             {
  47.                 if (i == pyramid.Length - 1)
  48.                 {
  49.                     path[i][j] = new int[] { pyramid[i][j] };
  50.                 }
  51.                 else
  52.                 {
  53.                     int[] leftPath = path[i + 1][j];
  54.                     int[] rightPath = path[i + 1][j + 1];
  55.                     if (Sum(leftPath) > Sum(rightPath))
  56.                     {
  57.                         path[i][j] = new int[] { pyramid[i][j] }.Concat(leftPath).ToArray();
  58.                     }
  59.                     else
  60.                     {
  61.                         path[i][j] = new int[] { pyramid[i][j] }.Concat(rightPath).ToArray();
  62.                     }
  63.                 }
  64.             }
  65.         }
  66.  
  67.         int longestPathSum = Sum(path[0][0]);
  68.  
  69.         Console.WriteLine("Longest Path Sum: " + longestPathSum);
  70.         Console.WriteLine("Longest Path: ");
  71.  
  72.  
  73.         foreach (var tempPath in path[0][0])
  74.         {
  75.             Console.WriteLine(tempPath);
  76.         }
  77.     }
  78.  
  79.     static int Sum(int[] array)
  80.     {
  81.         int sum = 0;
  82.         foreach (int num in array)
  83.         {
  84.             sum += num;
  85.         }
  86.         return sum;
  87.     }
  88. }
  89.