How to resolve the algorithm Maximum triangle path sum step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Maximum triangle path sum step by step in the C# programming language

Table of Contents

Problem Statement

Starting from the top of a pyramid of numbers like this, you can walk down going one step on the right or on the left, until you reach the bottom row: One of such walks is 55 - 94 - 30 - 26. You can compute the total of the numbers you have seen in such walk, in this case it's 205. Your problem is to find the maximum total among all possible paths from the top to the bottom row of the triangle. In the little example above it's 321.

Find the maximum total in the triangle below: Such numbers can be included in the solution code, or read from a "triangle.txt" file. This task is derived from the Euler Problem #18.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Maximum triangle path sum step by step in the C# programming language

The code is a program written in C# programming language that calculates the maximum total of a triangular array of numbers, in this case, the input is a string that contains the numbers in the array. It iterates over the input string, converting the numbers to integers and storing them in a 2 dimensional array. It then iterates over the array starting from the last row and summing the maximum of the two adjacent numbers in the next row, until it reaches the first row and calculates the maximum sum. The output is the maximum sum.

Source code in the csharp programming language

using System;

namespace RosetaCode
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int[,] list = new int[18,19];
			string input = @"55
	                        94 48
	                       95 30 96
	                     77 71 26 67
	                    97 13 76 38 45
	                  07 36 79 16 37 68
	                 48 07 09 18 70 26 06
	               18 72 79 46 59 79 29 90
	              20 76 87 11 32 07 07 49 18
	            27 83 58 35 71 11 25 57 29 85
	           14 64 36 96 27 11 58 56 92 18 55
	         02 90 03 60 48 49 41 46 33 36 47 23
	        92 50 48 02 36 59 42 79 72 20 82 77 42
	      56 78 38 80 39 75 02 71 66 66 01 03 55 72
	     44 25 67 84 71 67 11 61 40 57 58 89 40 56 36
	   85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52
	  06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15
	27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
			var charArray = input.Split ('\n');

			for (int i=0; i < charArray.Length; i++) {
				var numArr = charArray[i].Trim().Split(' ');

				for (int j = 0; j<numArr.Length; j++)
				{
					int number = Convert.ToInt32 (numArr[j]);
					list [i, j] = number;
				}
			}

			for (int i = 16; i >= 0; i--) {
				for (int j = 0; j < 18; j++) {
					list[i,j] = Math.Max(list[i, j] + list[i+1, j], list[i,j] + list[i+1, j+1]);
				}
			}
			Console.WriteLine (string.Format("Maximum total: {0}", list [0, 0]));
		}
	}
}

You may also check:How to resolve the algorithm Sorting algorithms/Pancake sort step by step in the Ada programming language
You may also check:How to resolve the algorithm Primality by trial division step by step in the Befunge programming language
You may also check:How to resolve the algorithm Reverse a string step by step in the Ruby programming language
You may also check:How to resolve the algorithm Determine if a string has all unique characters step by step in the Python programming language
You may also check:How to resolve the algorithm Lucas-Lehmer test step by step in the uBasic/4tH programming language