Maximum Interval Sum

Given a array of natural numbers, we have to find the maximum interval sum.
5    5   -1    5    5
Now we have these intervals (5 + 5), ( 5 + 5 + (-1)), (5 + 5 + (-1) + 5), (5 + 5 + (-1) + 5 + 5). 
Which interval has maximum sum?
(5 + 5) = 10
( 5 + 5 + (-1)) = 9
(5 + 5 + (-1) + 5) = 14
(5 + 5 + (-1) + 5 + 5) = 19
So, the last interval has maximum sum. These type of problems are called Maximum Interval Sum.
C++ implementation:

#include <iostream>
using namespace std;
const int INF = (-(1<<30));  // negative infinity
int MIS( ) {
    sum = 0; // initially sum is 0
    Max = -INF; // Maximum is less than 0
    for( i=0; i<N; i++ ) {
       sum += A[i]; // "A[]" array of intejars
        if( sum > Max ) Max = sum;
        if( sum < 0 ) sum = 0;  // sum below 0 is not useful, right?
    }
    return Max;
}

Message Print in Assembly Language

TITLE PRINTING HABIJABI

.MODEL SMALL    

.STACK 100H   

.DATA
MSG  DB 'Take Input: $'
MSG1 DB 'First Value: $'
MSG2 DB 'Second Value: $'
A    DB 5
B    DB ?

MAIN PROC
; initializing data segment  
    MOV AX, @DATA
    MOV DS, AX  ; initialized :D 
    
; display message
    LEA DX, MSG
    MOV AH, 9  ; message print function
    INT 21h  
    
; input 
    MOV AH, 1
    INT 21h
    MOV B, AL
    
; new line
    MOV AH, 2
    MOV DL, 0DH
    INT 21H
    MOV DL, 0AH
    INT 21H   
    
; display message1
    LEA DX, MSG1
    MOV AH, 9  ; message print function
    INT 21h
    
; display A
    MOV AH, 2
    MOV DL, A
    INT 21h
    
; new line
    MOV AH, 2
    MOV DL, 0DH
    INT 21H
    MOV DL, 0AH
    INT 21H   
    
; display message2
    LEA DX, MSG2
    MOV AH, 9  ; message print function
    INT 21h
    
; display B 
    MOV AH, 2
    MOV DL, B
    INT 21h
    
; return to DOS

    MOV AH, 4CH
    INT 21h
    
MAIN ENDP
    END MAIN

Maximum Sum Sub Matrix

Problem:

        Given m*n matrix. We have to find a sub-matrix which have maximum sum. Values of the matrix can be both positive and negative.

Idea:

      Lets start with an example then we will generate our idea. Suppose we have 4*4 matrix as below:
    [ initial matrix ] 
-1      2     3      10          
 5      9    -7       6
 0    -1     -3     -5
 7     5   -18       2

Now we add first column with second column. So, the matrix became like this:
-1      1     3      10
 5     14    -7       6
 0    -1     -3     -5
 7    12   -18       2
Now add second column with third column and the third column with last column. Then, the matrix will look like:
-1      1     4      14
 5     14     7      13
 0    -1     -4      -9
 7    12    -6      -4

Now the row addition part. Add first row with second, then add second with third, then third with last. Finally, the matrix will be:
-1      1      4      14
 5     15    11     27
 0     14     7      18
 7     26     1      14

Our matrix is ready to manipulate.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Definitely, we can say form this matrix that value of every cell is the sum of (0,0) to that cell. Say, (1,1) is 15 is the sum of (0,0), (0,1), (1,0) and (1,1) cells that is 15 i.e. ( -1+2+5+9 ) = 15. This property makes our idea easier. 

       In this matrix, the maximum sum is the middle sub-matrix. ( 15 + 11 + 14 + 7 ) = 37.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We are very closer to our solution. Now, see carefully. Cell (2,2) has cumulative sum form cell (0,0) to (2,2).  

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We can subtract the sum of cell (0,0) to (0,2) from this result. 

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Again, we subtract sum of cell (0,0) to (2, 0) from the last result.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Have we finished ? No. Look at the matrix above carefully. We have subtract cell (0,0) from the actual result  twice. It should be once. Finally, add the (0,0) cell to actual result and we get our maximum sum sub-matrix.