Poj Solution 3176

http://poj.org/problem?id=3176

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
        int height = cin.nextInt();   
        int[][] tree = new int[height][height];    
        int[][] max = new int[height][height];   
        int maxValue = 0;   
        int left, right = 0;   
           
        for(int i = 0; i < height; i++)   
        {   
            for(int j = 0; j <= i; j++)   
            {   
                tree[i][j] = cin.nextInt();   
//              System.out.print(tree[i][j] + " ");   
            }   
//          System.out.println("n");   
        }   
           
        max[0][0] = tree[0][0];   
           
  
           
        for(int i = 1; i < height; i++)   
        {   
            for(int j = 0; j <= i; j++)   
            {   
                if(j == 0)   
                    max[i][j] = max[i-1][j] + tree[i][j];   
                else if(j == i)   
                    max[i][j] = max[i-1][j-1] + tree[i][j];   
                else  
                {   
                    if(max[i-1][j-1] >= max[i-1][j])   
                        max[i][j] = max[i-1][j-1] + tree[i][j];   
                    else  
                        max[i][j] = max[i-1][j] + tree[i][j];   
                }   
            }   
        }   
           
        for(int j = 0; j < height; j++)   
        {   
            if(max[height-1][j] > maxValue)   
                maxValue = max[height-1][j];   
        }   
           
        System.out.println(maxValue);   
           
  
    }   
  
}  

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *