In this Poat, we will solve HackerRank Matrix Land Problem Solution.
You are playing a matrix-based game with the following setup and rules:
- You are given a matrix A with n rows and m columns. Each cell contains some points. When a player passes a cell their score increases by the number written in that cell and the number in the cell becomes 0. (If the cell number is positive their score increases, otherwise it decreases.)
- The player starts from any cell in the first row and can move left, right or down.
- The game is over when the player reaches the last row and stops moving.
Print the maximum score that the player can get.
Output Format
Print the maximum score that the player can get.
Sample Input 0
4 5
1 2 3 -1 -2
-5 -8 -1 2 -150
1 2 3 -250 100
1 1 1 1 20Sample Output 0
37
Matrix Land C Solution
#include <stdio.h>
#include <stdlib.h>
int max(int x,int y);
int N,*table[4000000],*dp,*tdp,*left_sum,*right_sum,*dp_left_tree;
int main(){
int n,m,ma,total,i,j;
scanf("%d%d",&n,&m);
dp=(int*)malloc(m*sizeof(int));
tdp=(int*)malloc(m*sizeof(int));
left_sum=(int*)malloc(m*sizeof(int));
right_sum=(int*)malloc(m*sizeof(int));
dp_left_tree=(int*)malloc(m*sizeof(int));
for(i=0;i<n;i++)
table[i]=(int*)malloc(m*sizeof(int));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&table[i][j]);
for(i=0;i<n;i++){
for(j=total=0;j<m;j++){
if(j)
left_sum[j]=table[i][j]+left_sum[j-1];
else
left_sum[j]=table[i][j];
total+=table[i][j];
}
for(j=m-1;j>=0;j--)
if(j!=m-1)
right_sum[j]=table[i][j]+right_sum[j+1];
else
right_sum[j]=table[i][j];
for(j=m-2;j>=0;j--)
left_sum[j]=max(left_sum[j],left_sum[j+1]);
for(j=1;j<m;j++)
right_sum[j]=max(right_sum[j],right_sum[j-1]);
if(i){
for(j=0;j<m;j++)
dp_left_tree[j]=dp[j]+left_sum[j];
for(j=m-2;j>=0;j--)
dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j+1]);
for(j=0;j<m;j++)
tdp[j]=right_sum[j]+dp_left_tree[j]-total;
for(j=0;j<m;j++)
dp_left_tree[j]=dp[j]+right_sum[j];
for(j=1;j<m;j++)
dp_left_tree[j]=max(dp_left_tree[j],dp_left_tree[j-1]);
for(j=0;j<m;j++){
if(left_sum[j]+dp_left_tree[j]-total>tdp[j])
tdp[j]=left_sum[j]+dp_left_tree[j]-total;
}
for(j=0;j<m;j++)
dp[j]=tdp[j];
}
else
for(j=0;j<m;j++)
dp[j]=left_sum[j]+right_sum[j]-total;
}
for(i=0,ma=-1000000001;i<m;i++)
if(dp[i]>ma)
ma=dp[i];
printf("%d",ma);
return 0;
}
int max(int x,int y){
return (x>y)?x:y;
}Matrix Land C++ Solution
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
#define INF INT_MAX/2
#define def -INF
template<class V, int NV> struct SegTree { //[l,r)
V comp(V& l, V& r) { return max(l,r); };
vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
V get(int x,int y,int l=0,int r=NV,int k=1){if(r<=x||y<=l)return def;if(x<=l&&r<=y)return val[k];
auto a=get(x,y,l,(l+r)/2,k*2);auto b=get(x,y,(l+r)/2,r,k*2+1);return comp(a,b);}
void update(int i, V v) { i+=NV;val[i]=v;while(i>1)i>>=1,val[i]=comp(val[i*2],val[i*2+1]); }
void add(int i, V v) { update(i, val[i + NV] + v); }
int operator[](int x) { return get(x, x + 1); }};
int H, W, A[4010101], _B[4010101], C[4010101], D[4010101];
int *B;
SegTree<int, 1 << 22> st;
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> H >> W;
B = _B + 1;
vector<int> dp(W, 0);
rep(y, 0, H) {
rep(x, 0, W) cin >> A[x];
vector<int> pd(W, -INF);
rep(_, 0, 2) {
rep(x, 0, W) B[x] = A[x];
rep(x, 1, W) B[x] += B[x - 1];
int ma = 0;
rep(x, 0, W) {
ma += A[x];
if (ma < 0) ma = 0;
C[x + 1] = ma;
}
ma = 0;
rrep(x, W - 1, 1) {
ma += A[x];
if (ma < 0) ma = 0;
D[x - 1] = ma;
}
rep(x, 0, W) st.update(x, dp[x] - B[x - 1] + C[x]);
rep(x, 0, W) {
int ma = st.get(0, x + 1);
pd[x] = max(pd[x], ma + B[x] + D[x]);
}
reverse(dp.begin(), dp.end());
reverse(pd.begin(), pd.end());
reverse(A, A + W);
}
swap(dp, pd);
//rep(x, 0, W) printf("%d\t", dp[x]); printf("\n");
}
int ans = -INF;
rep(x, 0, W) ans = max(ans, dp[x]);
cout << ans << endl;
}Matrix Land C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Solution {
static int matrixLand(int[][] mat)
{
int n = mat.Length;
int m = mat[0].Length;
int[] last = new int[m];
int[] curr = new int[m];
int[] currLeft = new int[m];
int[] currRight = new int[m];
checked
{
long[] leftKadane = new long[m];
long[] rightKadane = new long[m];
for (int i = n - 1; i >= 0; i--)
{
long cur = 0;
for (int j = 0; j < m; j++)
{
cur = cur + mat[i][j];
if (cur < mat[i][j])
{
cur = mat[i][j];
}
leftKadane[j] = cur;
}
cur = 0;
for (int j = m - 1; j >= 0; j--)
{
cur = cur + mat[i][j];
if (cur < mat[i][j])
{
cur = mat[i][j];
}
rightKadane[j] = cur;
}
for (int j = 0; j < m; j++)
{
var cand1 = (long)(j - 1 >= 0 ? currLeft[j-1] : int.MinValue) + mat[i][j];
var cand2 = (long)(i + 1 == n ? 0 : last[j]) + leftKadane[j];
currLeft[j] = (int)Math.Max(Math.Max(cand1, int.MinValue), Math.Max(cand2, int.MinValue));
}
for (int j = m - 1; j >= 0; j--)
{
var cand1 = (long)(j + 1 < m ? currRight[j + 1] : int.MinValue) + mat[i][j];
var cand2 = (long)(i + 1 == n ? 0 : last[j]) + rightKadane[j];
currRight[j] = (int)Math.Max(Math.Max(cand1, int.MinValue), Math.Max(cand2, int.MinValue));
}
for (int j = 0; j < m; j++)
{
long rightCand = (long)currRight[j] + leftKadane[j] - mat[i][j];
long leftCand = (long)currLeft[j] + rightKadane[j] - mat[i][j];
curr[j] = (int)Math.Max(Math.Max(rightCand, int.MinValue), Math.Max(leftCand, int.MinValue));
}
var tmp = curr;
curr = last;
last = tmp;
}
int res = int.MinValue;
for (int i = 0; i < m; i++)
{
res = Math.Max(res, last[i]);
}
return res;
}
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] nm = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(nm[0]);
int m = Convert.ToInt32(nm[1]);
int[][] A = new int[n][];
for (int i = 0; i < n; i++) {
A[i] = Array.ConvertAll(Console.ReadLine().Split(' '), ATemp => Convert.ToInt32(ATemp));
}
int result = matrixLand(A);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Matrix Land Java Solution
import java.io.*;
import java.util.*;
public class Solution {
static int matrixLand(int[][] grid) {
int m = grid[0].length;
int[][] dp = new int[grid.length][m];
int[] msl = new int[m];
int[] msr = new int[m];
int[] mslit = new int[m];
int[] msrit = new int[m];
for (int i = 0; i < grid.length; i++) {
Arrays.fill(msl, Math.max(grid[i][0], 0));
for (int j = 1; j < m; j++) {
msl[j] = Math.max(msl[j-1] + grid[i][j], 0);
}
Arrays.fill(msr, Math.max(grid[i][m-1], 0));
for (int j = 1; j < m; j++) {
msr[m-1-j] = Math.max(msr[m-j]+grid[i][m-1-j], 0);
}
Arrays.fill(mslit, grid[i][0]);
if (i > 0) {
mslit[0] += dp[i-1][0];
}
dp[i][0] = mslit[0]+msr[1];
for (int j = 1; j < m; j++) {
int top = i==0 ? 0 : dp[i-1][j];
mslit[j] = Math.max(mslit[j-1], top+msl[j-1])+grid[i][j];
int val = j+2>m ? 0 : msr[j+1];
dp[i][j] = mslit[j] + val;
}
Arrays.fill(msrit, grid[i][m-1]);
if (i > 0) {
msrit[m-1] += dp[i-1][m-1];
}
dp[i][m-1] = Math.max(dp[i][m-1], msrit[m-1]+msl[m-2]);
for (int j = 1; j < m; j++) {
int top = i==0 ? 0 : dp[i-1][m-1-j];
msrit[m-1-j] = Math.max(msrit[m-j], top+msr[m-j])+grid[i][m-1-j];
int val = j+2>m ? 0 : msl[m-1-j-1];
dp[i][m-1-j] = Math.max(dp[i][m-1-j], msrit[m-1-j] + val);
}
}
int result = dp[grid.length-1][0];
for (int j = 1; j < m; j++) {
result = Math.max(result, dp[grid.length-1][j]);
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
if (m==1) {
int result = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int item = Integer.parseInt(st.nextToken());
result += item;
}
bw.write(String.valueOf(result));
} else {
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int item = Integer.parseInt(st.nextToken());
a[i][j] = item;
}
}
int result = matrixLand(a);
bw.write(String.valueOf(result));
}
bw.newLine();
bw.close();
br.close();
}
}
Matrix Land JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'matrixLand' function below.
*
* The function is expected to return an INTEGER.
* The function accepts 2D_INTEGER_ARRAY A as parameter.
*/
function calculateMatrixLandDistance(matrixLand, rowLength, columnLength) {
let iMatrix = Array(columnLength), leftToRight = Array(columnLength), rightToLeft = Array(columnLength), maxLeftToRight = Array(columnLength), maxRightToLeft = Array(columnLength), distanceMatrix = Array.from(Array(rowLength), () => new Array(columnLength).fill(0));
for (let i = 0; i < rowLength; i++) {
iMatrix = matrixLand[i];
let vl = 0, vr = 0;
for (let j = 0; j < columnLength; j++) {
vl = leftToRight[j] = Math.max(vl + iMatrix[j], iMatrix[j]);
vr = rightToLeft[columnLength - j - 1] = Math.max(vr + iMatrix[columnLength - j - 1], iMatrix[columnLength - j - 1]);
}
vl = vr = Number.MIN_SAFE_INTEGER;
let index = (i - 1 < 0) ? 0: i - 1;
for (let j = 0; j < columnLength; j++) {
vl = maxLeftToRight[j] = Math.max(vl + iMatrix[j], distanceMatrix[index][j] + leftToRight[j]);
vr = maxRightToLeft[columnLength - j - 1] = Math.max(vr + iMatrix[columnLength - j - 1], distanceMatrix[index][columnLength - j - 1] + rightToLeft[columnLength - j - 1]);
}
for (let j = 0; j < columnLength; j++) {
distanceMatrix[i][j] = Math.max(
maxLeftToRight[j] + (j + 1 < columnLength ? Math.max(rightToLeft[j + 1], 0) : 0),
maxRightToLeft[j] + (j - 1 < columnLength && j-1>=0 ? Math.max(leftToRight[j - 1], 0) : 0)
);
}
}
let answer = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < columnLength; i++) {
answer = Math.max(answer, distanceMatrix[rowLength-1][i]);
}
return answer;
// let matrixLand = A;
// let rowLength = matrixLand.length;
// let columnLength = matrixLand[0].length;
// let distanceMatrix = Array.from(Array(matrixLand.length), () => new Array(matrixLand[0].length).fill(Number.MIN_SAFE_INTEGER));
// let tempDistanceMat = [];
// for(let r = 0; r < rowLength; r++) {
// for (let c = 0; c < columnLength; c++) {
// tempDistanceMat = Array(columnLength).fill(Number.MIN_SAFE_INTEGER);
// let downDistance = 0;
// if (r !== 0) {
// downDistance = distanceMatrix[r - 1][c];
// }
// tempDistanceMat[c] = matrixLand[r][c] + downDistance;
// leftSubarray(r, c, tempDistanceMat, matrixLand);
// rightSubarray(r, c, tempDistanceMat, matrixLand, columnLength);
// compareDistanceMatrix(distanceMatrix, tempDistanceMat, r, columnLength);
// }
// }
// return Math.max(...distanceMatrix[rowLength - 1]);
}
// function leftSubarray(r, c, tempDistanceMat, matrixLand) {
// let col = c - 1;
// for (; col >= 0; col--) {
// if (tempDistanceMat[col] < tempDistanceMat[col + 1] + matrixLand[r][col])
// tempDistanceMat[col] = tempDistanceMat[col + 1] + matrixLand[r][col];
// }
// col = 0;
// while (col < c) {
// if (tempDistanceMat[col+1] < tempDistanceMat[col])
// tempDistanceMat[col + 1] = tempDistanceMat[col];
// col++;
// }
// }
// function rightSubarray(r, c, tempDistanceMat, matrixLand, columnLength) {
// let col = c + 1;
// for (; col < columnLength; col++) {
// if(tempDistanceMat[col] < tempDistanceMat[col - 1] + matrixLand[r][col])
// tempDistanceMat[col] = tempDistanceMat[col - 1] + matrixLand[r][col];
// }
// col = columnLength;
// while (col > c) {
// if(tempDistanceMat[col - 1] < tempDistanceMat[col])
// tempDistanceMat[col - 1] = tempDistanceMat[col];
// col--;
// }
// }
// function compareDistanceMatrix(distanceMatrix, tempDistanceMat, r, columnLength) {
// for (let col = 0; col < columnLength; col++) {
// if (distanceMatrix[r][col] < tempDistanceMat[col])
// distanceMatrix[r][col] = tempDistanceMat[col];
// }
// }
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const n = parseInt(firstMultipleInput[0], 10);
const m = parseInt(firstMultipleInput[1], 10);
let A = Array(n);
for (let i = 0; i < n; i++) {
A[i] = readLine().replace(/\s+$/g, '').split(' ').map(ATemp => parseInt(ATemp, 10));
}
const result = calculateMatrixLandDistance(A, n, m);
ws.write(result + '\n');
ws.end();
}Matrix Land Python Solution
import os, sys
with open('progIn.txt', 'w') as file:
for line in sys.stdin:
file.write(line)
prog = r"""
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <utility>
using namespace std;
int main() {
int m, n;
scanf("%d %d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
for ( int i = 0; i < n; ++i ) for ( int j = 0; j < m; ++j ) scanf("%d", &a[i][j]);
vector<long> foundation (m);
for ( int i = n - 1; i > -1; --i ) {
vector<int> build = a[i];
multiset<long> forwards, backwards;
vector<int> pf(m), pb(m), l(m), r(m);
pf[0] = build[0]; pb[m-1] = build[m-1];
for ( int j = 1; j < m; ++j ) {
pf[j] = build[j] + pf[j-1];
}
for ( int j = m - 2; j > -1; --j ) {
pb[j] = build[j] + pb[j+1];
}
r[m-1] = m - 1;
for ( int j = m - 2; j > -1; --j ) {
if ( pf[r[j+1]] <= pf[j] ) {
r[j] = j;
} else {
r[j] = r[j+1];
}
}
l[0] = 0;
for ( int j = 1; j < m; ++j ) {
if ( pb[l[j-1]] <= pb[j] ) {
l[j] = j;
} else {
l[j] = l[j-1];
}
}
vector<long> foundation2(m);
int offsetf = 0, offsetb = 0;
//when we fill these guys up, we need to add: prefix, foundation, AND RIGHT BOUND.
for ( int j = 0; j < m; ++j ) {
long val = pf[j] + foundation[j];
if ( j < m - 1 ) {
val += pf[r[j]] - pf[j];
// cout << "ROW " << i << " COL " << j << ": ADDED " << pf[r[j]] - pf[j] << ", since r[j] = " << r[j]
// << " and pf[r[j]] = " << pf[r[j]] << " and pf[j] = " << pf[j] << endl;
}
// cout << "ROW " << i << " COL " << j << ": " << "Inserting (FB) = " << val << endl;
forwards.insert(val);
}
backwards.insert(pb[0] + foundation[0]);
foundation2[0] = *(forwards.rbegin());
//cout << "pf: ";
//for ( auto u : pf ) cout << u << ' ';
//cout << endl;
//cout << "LJ: ";
//for ( auto u : l ) cout << u << ' ';
//cout << endl;
for ( int j = 1; j < m; ++j ) {
//cout << "-----------" << endl;
offsetf = -pf[j-1];
long erasable = pf[j-1] + foundation[j-1] + pf[r[j-1]] - pf[j-1];
// cout << "ALSO SIZE IS " << forwards.size() << "; and just erased one!" << endl;
forwards.erase(forwards.find(erasable));
long val = pb[j] + foundation[j];
int left_bonus = j == l[j]
? (0)
: l[j] == 0
? pf[j-1]
: pf[j-1] - pf[l[j-1]-1];
val += left_bonus;
backwards.insert(val);
offsetb = j >= m - 1? 0 : -pb[j+1];
/*if ( j != l[j] && l[j] != 0 ) {
left_bonus = pf[j-1] - pf[l[j-1]];
} else {
cout << "keep debugging " << endl;
}*/
//cout << "left_bonus: " << left_bonus << endl;
int right_bonus = pf[r[j]] - pf[j];
// cout << "i: " << i << "; j: " << j << ";frb: " << *(forwards.rbegin()) << ";brb: " << *(backwards.rbegin()) << endl;
// cout<< "of: "<<offsetf<< "; ob: " << offsetb << endl;
// cout << "lb: " << left_bonus << "; rb: " << right_bonus << endl;
// cout << "lj: " << l[j] << "; rj: " << r[j] << endl;
foundation2[j] = forwards.size()
? max( *(forwards.rbegin()) + offsetf + left_bonus, *(backwards.rbegin()) + offsetb + right_bonus)
: left_bonus + *(backwards.rbegin()) + offsetb;
// cout << "computed value: " << foundation2[j] << endl;
}
// for ( auto u : foundation ) cout << u << ' ';
// cout << endl;
foundation = foundation2;
}
// for ( auto u : foundation ) cout << u << ' ';
// cout << endl;
long b = -2000000000;
for ( auto i : foundation ) b = max(b, i);
cout << b << endl;
}"""
if not os.path.isfile('compiled.txt'):
open('prog.cpp', 'w').write(prog)
os.system("g++ -std=c++17 -O3 -oprog prog.cpp")
open('compiled.txt', 'w').write('BRAH')
os.system("./prog < progIn.txt > progOut.txt")
print(open('progOut.txt', 'r').read().strip())
