Maximum path sum in matrix.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Given a matrix of N * M. Find the maximum path sum in matrix. The maximum path is sum of all elements from first row to last row where \n",
    "you are allowed to move only down or diagonally to left or right. You can start from any element in first row.\n",
    "\n",
    "Examples:\n",
    "\n",
    "Input : mat[][] = 10 10  2  0 20  4\n",
    "                   1  0  0 30  2  5\n",
    "                   0 10  4  0  2  0\n",
    "                   1  0  2 20  0  4\n",
    "Output : 74\n",
    "The maximum sum path is 20-30-4-20.\n",
    "\n",
    "Input : mat[][] = 1 2 3\n",
    "                  9 8 7\n",
    "                  4 5 6\n",
    "Output : 17\n",
    "The maximum sum path is 3-8-6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[10, 10, 2, 0, 20, 4], [11, 0, 0, 30, 2, 5], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 0, 30, 2, 5], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 30, 2, 5], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 2, 5], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 5], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [0, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 54, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 54, 56, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 54, 56, 74, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 54, 56, 74, 52, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [11, 10, 10, 50, 22, 25], [11, 21, 54, 50, 52, 25], [22, 54, 56, 74, 52, 56]]\n",
      "74\n"
     ]
    }
   ],
   "source": [
    "# Python 3 prorgam for finding max path in matrix \n",
    "# To calculate max path in matrix \n",
    "\n",
    "def findMaxPath(mat): \n",
    "\n",
    "    # To find max val in first row \n",
    "    res = -1\n",
    "    for i in range(M): \n",
    "        res = max(res, mat[0][i]) \n",
    "\n",
    "    for i in range(1, N): \n",
    "\n",
    "        res = -1\n",
    "        for j in range(M): \n",
    "\n",
    "            # When all paths are possible \n",
    "            if (j > 0 and j < M - 1): \n",
    "                mat[i][j] += max(mat[i - 1][j], \n",
    "                                max(mat[i - 1][j - 1], \n",
    "                                    mat[i - 1][j + 1])) \n",
    "                print(mat)\n",
    "\n",
    "            # When diagonal right is not possible \n",
    "            elif (j > 0): \n",
    "                mat[i][j] += max(mat[i - 1][j], \n",
    "                                mat[i - 1][j - 1]) \n",
    "                print(mat)\n",
    "\n",
    "            # When diagonal left is not possible \n",
    "            elif (j < M - 1): \n",
    "                mat[i][j] += max(mat[i - 1][j], \n",
    "                                mat[i - 1][j + 1]) \n",
    "                print(mat)\n",
    "\n",
    "            # Store max path sum \n",
    "            res = max(mat[i][j], res) \n",
    "    return res \n",
    "\n",
    "# Driver program to check findMaxPath \n",
    "N=4\n",
    "M=6\n",
    "mat = ([[ 10, 10, 2, 0, 20, 4 ], \n",
    "        [ 1, 0, 0, 30, 2, 5 ], \n",
    "        [ 0, 10, 4, 0, 2, 0 ], \n",
    "        [ 1, 0, 2, 20, 0, 4 ]]) \n",
    "                \n",
    "print(findMaxPath(mat)) \n",
    "\n",
    "# This code is contributed by Azkia Anam. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "for j in range(10,0,-1):\n",
    "    print(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3], [1, 2, 3]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [[1,2,3],[4,5,6]]\n",
    "a[1] = [1,2,3]\n",
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findmaxpath(mat):\n",
    "    col_size = len(mat)\n",
    "    print('column size',col_size)\n",
    "    row_size = len(mat[col_size-1])\n",
    "    print('row size',row_size)\n",
    "    dp = [[-1]*row_size for i in range(col_size)]\n",
    "    dp[col_size-1] = mat[col_size-1]\n",
    "    for row_num in range(col_size-2,-1,-1):\n",
    "        dp[row_num][0] = max(mat[row_num][0]+dp[row_num+1][0],mat[row_num][0]+dp[row_num+1][1])\n",
    "        print(dp)\n",
    "        for col_num in range(1,row_size-1,1):\n",
    "            print(row_num,col_num)\n",
    "            dp[row_num][col_num] = max(mat[row_num][col_num]+dp[row_num+1][col_num],mat[row_num][col_num]+dp[row_num+1][col_num+1],mat[row_num][col_num]+dp[row_num+1][col_num-1])\n",
    "            print(dp)\n",
    "        dp[row_num][row_size-1] = max(mat[row_num][row_size-1]+dp[row_num+1][row_size-1],mat[row_num][row_size-1]+dp[row_num+1][row_size-2])\n",
    "        print(dp)\n",
    "    print(dp)\n",
    "    return max([max(l) for l in dp])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "mat = ([[ 10, 10, 2, 0, 20, 4 ], \n",
    "        [ 1, 0, 0, 30, 2, 5 ], \n",
    "        [ 0, 10, 4, 0, 2, 0 ], \n",
    "        [ 1, 0, 2, 20, 0, 4 ]]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "column size 4\n",
      "row size 6\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, -1, -1, -1, -1, -1], [1, 0, 2, 20, 0, 4]]\n",
      "2 1\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, 12, -1, -1, -1, -1], [1, 0, 2, 20, 0, 4]]\n",
      "2 2\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, 12, 24, -1, -1, -1], [1, 0, 2, 20, 0, 4]]\n",
      "2 3\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, 12, 24, 20, -1, -1], [1, 0, 2, 20, 0, 4]]\n",
      "2 4\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, 12, 24, 20, 22, -1], [1, 0, 2, 20, 0, 4]]\n",
      "[[-1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[-1, -1, -1, -1, -1, -1], [13, -1, -1, -1, -1, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 1\n",
      "[[-1, -1, -1, -1, -1, -1], [13, 24, -1, -1, -1, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 2\n",
      "[[-1, -1, -1, -1, -1, -1], [13, 24, 24, -1, -1, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 3\n",
      "[[-1, -1, -1, -1, -1, -1], [13, 24, 24, 54, -1, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 4\n",
      "[[-1, -1, -1, -1, -1, -1], [13, 24, 24, 54, 24, -1], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[-1, -1, -1, -1, -1, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, -1, -1, -1, -1, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 1\n",
      "[[34, 34, -1, -1, -1, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 2\n",
      "[[34, 34, 56, -1, -1, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 3\n",
      "[[34, 34, 56, 54, -1, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 4\n",
      "[[34, 34, 56, 54, 74, -1], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, 34, 56, 54, 74, 31], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, 34, 56, 54, 74, 31], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "74"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findmaxpath(mat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findmaxpath(mat):\n",
    "    col_size = len(mat)\n",
    "    print('column size',col_size)\n",
    "    row_size = len(mat[col_size-1])\n",
    "    print('row size',row_size)\n",
    "    for row_num in range(col_size-2,-1,-1):\n",
    "        mat[row_num][0] = max(mat[row_num][0]+mat[row_num+1][0],mat[row_num][0]+mat[row_num+1][1])\n",
    "        print(mat)\n",
    "        for col_num in range(1,row_size-1,1):\n",
    "            print(row_num,col_num)\n",
    "            mat[row_num][col_num] = max(mat[row_num][col_num]+mat[row_num+1][col_num],mat[row_num][col_num]+mat[row_num+1][col_num+1],mat[row_num][col_num]+mat[row_num+1][col_num-1])\n",
    "            print(mat)\n",
    "        mat[row_num][row_size-1] = max(mat[row_num][row_size-1]+mat[row_num+1][row_size-1],mat[row_num][row_size-1]+mat[row_num+1][row_size-2])\n",
    "        print(mat)\n",
    "    print(mat)\n",
    "    return max([max(l) for l in mat])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "column size 4\n",
      "row size 6\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 10, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "2 1\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 12, 4, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "2 2\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 12, 24, 0, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "2 3\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 12, 24, 20, 2, 0], [1, 0, 2, 20, 0, 4]]\n",
      "2 4\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 12, 24, 20, 22, 0], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [1, 0, 0, 30, 2, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [13, 0, 0, 30, 2, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 1\n",
      "[[10, 10, 2, 0, 20, 4], [13, 24, 0, 30, 2, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 2\n",
      "[[10, 10, 2, 0, 20, 4], [13, 24, 24, 30, 2, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 3\n",
      "[[10, 10, 2, 0, 20, 4], [13, 24, 24, 54, 2, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "1 4\n",
      "[[10, 10, 2, 0, 20, 4], [13, 24, 24, 54, 24, 5], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[10, 10, 2, 0, 20, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, 10, 2, 0, 20, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 1\n",
      "[[34, 34, 2, 0, 20, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 2\n",
      "[[34, 34, 56, 0, 20, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 3\n",
      "[[34, 34, 56, 54, 20, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "0 4\n",
      "[[34, 34, 56, 54, 74, 4], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, 34, 56, 54, 74, 31], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n",
      "[[34, 34, 56, 54, 74, 31], [13, 24, 24, 54, 24, 27], [1, 12, 24, 20, 22, 4], [1, 0, 2, 20, 0, 4]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "74"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findmaxpath(mat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}