CareerCup

array[0][0...N] = 0;
array[0...M][0]=0;
for i=1 to M
  for j=1 to N
     if(array[i-1][j] >= array[i][j-1])
            array[i][j] += array[i-1][j]
     else
           array[i][j] += array[i][j-1]

the maximum sum is stored in array[M][N]

/// Using Dynamic Programming
/// t[ix][iy] = map[ix-1][iy-1] + max(t[ix-1][iy], t[ix-1][iy])
inline int max(int a, int b)
{
return (a < b) ? b : a;
}

int apple_collect()
{
int map[4][4] = {
{10, 9, 1, 2},
{3, 4, 3, 4},
{1, 2, 5, 8},
{8, 2, 3, 5}
};

int t[5][5];
memset(t, 0, sizeof(t));
int ix = 0, iy = 0;
for(ix = 1; ix <= 4; ix ++)
{
for(iy = 1; iy <= 4; iy ++)
{
int mx = max(t[ix-1][iy], t[ix][iy-1]);
mx += map[ix-1][iy-1];
t[ix][iy] = mx;
}
}

return t[4][4];
}

ITERATIVE:

public static int[][] getMaximalCostMatrix(int[][] valueMatrix)
    {
        int[][] costMatrix= new int[valueMatrix.length][valueMatrix[0].length];
        costMatrix[0][0]= valueMatrix[0][0];
        for(int i=1; i<costMatrix.length; i++)
        {
            costMatrix[i][0]= valueMatrix[i][0] + costMatrix[i-1][0];
            costMatrix[0][i]= valueMatrix[0][i] + costMatrix[0][i-1];
        }        
        
        for(int i=1; i<costMatrix.length; i++)
        {
            costMatrix[i][i]= valueMatrix[i][i] + max(costMatrix[i-1][i], costMatrix[i][i-1]);
            
            for(int j=i+1; j<costMatrix.length; j++)
            {
                costMatrix[i][j]= valueMatrix[i][j] + max(costMatrix[i-1][j], costMatrix[i][j-1]);
                costMatrix[j][i]= valueMatrix[j][i]+ max(costMatrix[j-1][i], costMatrix[j][i-1]);
            }
        }
        
        return costMatrix;
    }

RECURSIVE

public static void getMaximalCostMatrix(int[][] valueMatrix, int[][] costMatrix, int i, int j)
    {
        if(i==0&&j==0)
            costMatrix[i][j]= valueMatrix[i][j];
        else
        {
            
        if(i-1>=0&&costMatrix[i-1][j]==0)
        getMaximalCostMatrix(valueMatrix, costMatrix, i-1, j);
        if(j-1>=0&&costMatrix[i][j-1]==0)
        getMaximalCostMatrix(valueMatrix, costMatrix, i, j-1);
        
        int p= i-1>=0?costMatrix[i-1][j]:0;
        int q= j-1>=0?costMatrix[i][j-1]:0;
        
        costMatrix[i][j]= valueMatrix[i][j] + max(p,q);
        }
    }

It can be done using Dynamic Programming, We will start with bottom right point and build it up.

Sounds like a DP problem.

I don't get the question in the first place. Don't you think that parsing the whole 2D array will give the maximum? Or I might be missing something?

Correction : the last line should not contain a + inside max()

this can be solved using modified dijkstra algorithm , just u gonna use max-priority queue in place of min and some more minor modifications... atleast that is wat i think!!!

#include<stdio.h>
#define max(a,b) ((a)>(b) ? (a) : (b))
int main(){
int a[1001][1001],m,n,i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			scanf("%d",&a[i][j]);
for(i=n-2;i>=0;i--)
	a[i][m-1]+=a[i+1][m-1];
for(j=m-2;j>=0;j--)
	a[n-1][j]+=a[n-1][j+1];
for(i=n-2;i>=0;i--)
	for(j=m-2;j>=0;j--)
		a[i][j]+=max(a[i+1][j],a[i][j+1]);
printf("%d\n",a[0][0]);
return 0;

}

let the ip array be a[m][n]
op=max sum int
---------------
i=j=0;
sum=0;
int fuc(i,j)
{
sum+=a[i][j]
if(i==m-1 && j==n-1)
return sum;
else
return max (fuc(a[i][j+1]) ,fuc(a[i+1][j])
}

please comment on the above code and let me kno if i'm right
-krPESIT

for(int i=1;i<4;i++)
for(int j=1;j<5;j++)
if(array[i-1][j]>=array[i][j-1])
array[i][j]+=array[i-1][j];
else
array[i][j]+=array[i][j-1];

How about this soln, simple recursion algo.

Function Signature Find(A, M, N, i, j, S)
A[M][N] - 2-D array
i,j - Starting coordinates(1,1) (I am assuming indexing from 1)
S - initially 0


Find(A, M, N, i, j, S)
{
if(i==M && j==N)
return S + A[i][j];
else
{
int S1=0, S2=0;
if(i<M)
{
S1 = Find(A, M, N, i+1, j, S + A[i][j]);
}

if(j<N)
{
S2 = Find(A, M, N, i, j+1, S + A[i][j]);
}

return S1>=S2 ? S1 : S2 ;
}
}

int n, m;
vector< vector<int> > dp(n, vector<int>(m, 0));
dp[0][0] = a[0][0];
for (int j=1; j < m; j++)
        dp[0][j] += dp[0][j-1];
for (int i=1; i < n; i++)
        dp[i][0] += dp[i-1][0];
for (int i=1; i < n; i++) for (int j=1; j < m; j++)
          dp[i][j] = a[i][j] + max(dp[i][j-1], dp[i-1][j]);

return dp[n-1][m-1];

public class CountingApples {
    int m,n;
    int[][] apples;
    int[][] collect;

    public CountingApples(int m, int n, int[][] apples) {
        this.m = m;
        this.n = n;
        this.apples = apples;
        this.collect = new int[m][n];
    }

    private int computeMaxApples() {
        for(int i=0 ;i<m; i++) {
            for(int j=0 ;j<n; j++) {
                collect[i][j] = apples[i][j] + Math.max((i>0) ? collect[i-1][j] : 0, (j>0)? collect[i][j-1] : 0);
            }
        }
        return collect[m-1][n-1];
    }

    public static void main(String[] args) {
        int[][] apples = {
                {1, 2, 3, 4},
                {1, 1, 1, 1},
                {9, 9, 9, 9}
        };
        CountingApples ca = new CountingApples(3,4, apples);
        System.out.println("Max apples: " + ca.computeMaxApples());
    }

}

class

How to submit code?

use

for all i from 0 to M
        for all j from 0 to N
            if i and j both 0 continue;
            else if only i is 0 apples[i][j] += apples[i][j-1]
            else if only j is 0 apples[i][j] += apples[i-1][j]
            else apples[i][j] += max( apples[i-1][j] + apples[i][j-1] )

the cell at extreme bottom-right will give the maximum apples that can be collected.

use djikstra algo