CareerCup

dynamic programming approach:
if matrix[i][j]=0,dp[i][j]==0
else,dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1,
traverse the matrix,and the maximum value of dp[i][j] is the answer.
time complexity O(m*n),space O(max(m,n)) (optimized )

int MaxConnectedOnes(vector<vector<int> >& A)
{
    int n=A.size();
    if(n<=0)return 0;
    int m=A[0].size();
    vector<int> dp(m+1);
    dp[0]=0;
    int maxCount=0;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(A[i][j-1]==0)dp[j]=0;
            else
            {
                dp[j]=max(dp[j],dp[j-1])+1;
                maxCount=max(maxCount,dp[j]);
            }
        }
    }
    return maxCount;
}

Binary Tree Approach:
=====================
int MaxConnect(int **A, int R, int C)
{
    int i, j, MAX = 0, Temp_MAX = 0;
    for(i = 0; i<R; i++)
        for(j = 0; j<C; j++) {
            if(A[i][j] == 1) {
                if(i-1>=0 && j-1>=0 && A[i-1][j] == 0 && A[i][j-1] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1>=0 && j-1 < 0 && A[i-1][j] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1<0 && j-1>=0 && A[i][j-1] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1<0 && j-1<0) {
                    Temp_MAX = GetLength(A, i, j);
                }
                if(Temp_MAX > MAX)
                    MAX = Temp_MAX;
            }//if(A[i][j] == 1)
        }
        return MAX;
}

int GetLength(int **A, int r, int c){
    int down, right;

    if(A[r][c] == 1) {
    down = GetLength(A, r+1, c);
    right = GetLength(A, r, c+1);
    return 1+ max(down, right);
    } else {
        return 0;
    }
}

T(N) = O(N*L)
N: Size of Matrix i.e. N = Row X Culumn
L: Length of the connected 1

Dynamic Programming Approach:
=============================
int MaxConnect(int **A, int R, int C){
    int Buff[R+1][C+1], MAX = 0;
    for(int i=0; i<R+1; i++)
        for(int j=0; j<C+1; j++)
            Buff[i][j] = 0;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(A[i][j] == 1){
                Buff[i+1][j+1] = 1 + max(Buff[i-1][j], Buff[i][j-1]);
                if (Buff[i+1][j+1] > MAX)
                    MAX = Buff[i+1][j+1];
            }
	}
    }
    return MAX;
}

T(N) = O(N)
    N: Size of Matrix i.e. N = Row X Culumn
S(N) = Size of Matrix i.e. N = Row X Culumn

int MaxCount(int *a, i, j)
{
if(a[i][j] == 0)
return 0;
else
return Max(MaxCount(a[i+1, j]), MaxCount(a[i,j+1])) + 1;
}
}

Dynamic Programming

def getMaxPath(matrix):
    m, n = len(matrix), len(matrix[0])
    maxPath = [[0] * (n+1) for i in range(m+1)]
    maxStreak = 0
        
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if(matrix[i][j] == 1):
                maxPath[i][j] = 1 + max(maxPath[i+1][j], maxPath[i][j+1])
                if(maxStreak < maxPath[i][j]):
                    maxStreak = maxPath[i][j]
    return maxStreak
                    
print(getMaxPath([[0, 0, 1, 1], [1, 1, 1, 0], [1, 0, 1, 0], [0, 1, 0, 1]]))

Here's my solution using basic DP :

I would add the following to give complete solution :

int& getMaxCount(int* a, int N, int M){
int max = 0;
for(int i = M-2 ; i >= 0 ; i--)
for(int j = N-2 ; j >= 0 ; j--){
if( a[i][j] == 1 ){
a[i][j] += a[i+1][j]>a[i][j+1]?a[i+1][j]:a[i][j+1];
}
if( a[i][j] > max )
max = a[i][j];
}
return max;

}

#include<stdio.h>
#include<conio.h>
int max(int x, int y)
{
    if(x>=y)
    return x;
    else
    return y;
}
int main()
{
    int a[][4]={0, 0, 1, 1,
                1, 1, 1, 0,
                1, 0, 1, 0,
                0, 1, 0, 1,};
    int i,j;
    int max=0;
    for(i=1;i<4;i++)
    {   // First column
      if(a[0][i]!=0){
         a[0][i]=a[0][i]+a[0][i-1];
         if(a[0][i]>max)
         max=a[0][i];
         }
      else
         a[0][i]=0;
    }
     for(j=1;i<4;i++)
    { //First row
      if(a[j][0]!=0){
         a[j][0]=a[j][0]+a[j-1][0];
         if(a[j][0]>max)
         max=a[j][0];
         }
      else
         a[j][0]=0;
    }
    for(i=1;i<4;i++)
    {
      for(j=1;j<4;j++)
      {
         if(a[i][j]!=0)
         {
            a[i][j]=a[i-1][j]+a[i][j-1]+a[i][j];
            if(a[i][j]>max)
         max=a[i][j];
         }
         else
         {
             a[i][j]=0;//max(a[i-1][j],a[i][j-1]);
         }
      }
    }
 for(i=0;i<4;i++)
    {
      for(j=0;j<4;j++)
      {
         printf("%d",a[i][j]);
      }
    printf("\n");
}
        
printf("Largest block of 1 is: %d",max);
getchar();
getchar();
return 0;
}

package com.algorithms;

public class MaxPathBinaryArray {
public static void main(String[] args){
int[][] a = {
{ 0, 0, 1, 1 },
{ 1, 1 ,1, 0 },
{ 1, 0, 1 ,0 },
{ 0, 1, 0, 1 }
};
int ROWS = 4;
int COLS = 4;
boolean sequence = false;
int currMax = 0;
int max = 0;
for ( int i = 0; i < ROWS; i++){
currMax = 0;
sequence = false;
for (int j = 0; j < COLS; j++){
if ( a[i][j] == 1 && !sequence){
currMax = 0;
if ( i+1 < ROWS ){
if ( a[i+1][j] == 1){
currMax++;
}
}
sequence = true;
}else if ( a[i][j] == 1 && sequence){
currMax++;
if ( i+1 < ROWS){
if ( a[i+1][j] == 1){
currMax++;
}
}
sequence = true;
}else{
sequence = false;
if ( currMax != 0){
if ( max < currMax){
max = currMax;
}
}
}
}
if ( currMax != 0){
if ( max < currMax){
max = currMax;
}
}

}
System.out.println("Max Path is : "+max);
}
}