Maximum Candies Codechef Solution

Hello Programmers In this post, you will know how to solve the Maximum Candies Codechef Solution.

Maximum Candies Codechef Solution
Maximum Candies Codechef Solutions

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem description

Impressed with Agnes' jumping skills, Gru has decided to build a new game for her.
Gru has laid out a grid of N x M tiles, and each tiles contains some (positive) number of candies.
The rules of the games are as following:
- Agnes starts from the tile (0, 0) // 0 based index
- She has to reach the tile (N-1, M-1)
- At a time she can either move in +x direction by 1 tile or in +y direction..
- She cannot  go left or  up .
- She can go from (0, 0) -> (N-1, M-1) only once.
See example below for the movement for more clarity
Now Agnes wants to collect maximum number of candies possible while playing the game. Can you help her out?
Example:
Consider the matrix of 4x3, she starts at (0,0) and collects all candies from (0, 0). Now she can move to (0, 1) or (1, 0).
More generically, allowed moves from (i, j) are
 - (i+1, j)  OR
 - (i, j+1)
Illegal moves
- (i-1, j)
- (i, j-1)

Input

First line contains number of tests - T.
Each test consists of following lines:
  First line contains two space separated positive integers N and M, representing the grid size
  Next N lines represents rows of the grid . Each of the N lines contains M integers. 

Output

Output a single integer that is equal to maximum candies that Agnes can collect.

Constraints

0 < T < 10
0 < N < 1000
0 < M < 1000

Example

Input

1
2 4
1 2 3 8
3 4 5 6

Output
20

Explanation

Example case 1.

N = 2, M = 4
First row a[0][0] = 1 a[0][1] = 2 a[0][2] = 3 a[0][3] = 8
Second row a[1][0] = 3 a[1][1] = 4 a[1][2] = 5 a[1][3] = 6
Objective reach from a[0][0] -> a[1][3]
Take the path:
a[0][0] -> a[0][1] -> a[0][2] -> a[0][3]-> a[1][3]
Answer = 1 + 2 + 3 + 8 + 6 = 20

Maximum Candies CodeChef Solutions in JAVA

import java.io.*;
import java.util.*;
class MaximizingCandies {
  public static long dp[][];
  public static void main(String argsp[]) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    while (t-- > 0) {
      int n = in.nextInt();
      int m = in.nextInt();
      long arr[][] = new long[n][m];
      dp = new long[n][m];
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          arr[i][j] = in.nextInt();
          dp[i][j] = Long.MIN_VALUE;
        }
      }
      dp[n - 1][m - 1] = arr[n - 1][m - 1];
      long answer = solve(arr, 0, 0);
      System.out.println(answer);
    }
    in.close();
  }
  public static long solve(long arr[][], int x, int y) {
    if (dp[x][y] > Integer.MIN_VALUE) return dp[x][y];
    int n = arr.length;
    int m = arr[0].length;
    if (x == n - 1) {
      dp[x][y] = arr[x][y] + solve(arr, x, y + 1);
    } else if (y == m - 1) {
      dp[x][y] = arr[x][y] + solve(arr, x + 1, y);
    } else {
      dp[x][y] = arr[x][y] + Math.max(solve(arr, x, y + 1), solve(arr, x + 1, y));
    }
    return dp[x][y];
  }
}

Maximum Candies CodeChef Solutions in CPP

//I_F_A
#include "bits/stdc++.h"
using namespace std;
#define N 1001
long long dp[N][N];
long long arr[N][N];
long long n,m;
long long solve(long long i,long long j){
	if(i == n && j == m){
		return arr[i][j];
	}
	if(dp[i][j] == INT_MAX){
		long long ans1 = arr[i][j] , ans2 = arr[i][j];
		if(i + 1 <= n){
			ans1 = ans1 + solve(i+1,j);
		}
		if(j + 1 <= m){
			ans2 = ans2 +solve(i,j+1);
		}
		dp[i][j] = max(ans1,ans2);
	}
	return dp[i][j];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin >> tc;
	while(tc--){
		cin >> n >> m;
		for(long long i=1;i<=n;i++){
			for(long long j=1;j<=m;j++){
				cin >> arr[i][j];
				dp[i][j] = INT_MAX;
			}
		}
		cout << solve(1,1) << endl;
	}
}

Maximum Candies Codechef Solutions in Python

from sys import stdin
def maxCost(cost, m, n):
    tc = [[0 for x in range(C)] for x in range(R)]
    tc[0][0] = cost[0][0]
    for i in range(1, m + 1):
        tc[i][0] = tc[i - 1][0] + cost[i][0]
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j - 1] + cost[0][j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = max(tc[i - 1][j - 1], tc[i - 1][j], tc[i][j - 1]) + cost[i][j]
    return tc[m][n]
for _ in range(int(stdin.readline())):
     R,C = map(int,stdin.readline().split())
     cost =[]
     for i in range(R):
         cost.append(list(map(int,stdin.readline().split())))
     print(maxCost(cost,R-1,C-1))
Ezoicreport this ad

Disclaimer: The above Problem (Maximum Candies) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Check Algorithm Codechef Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad