Friday, October 26, 2012

Simple Java Program to Write to a Zip File.

This Program takes a Zip file Directory and a Zip file name as Input.
'writeAsZip()' method writes an Array of Bytes as a Zip Entry to the Zip file.
Suppose a zip file 'D:\\test\\cb-1-zip.zip' is has two constituents, namely : 'a.txt' and 'b.png'
This zip File is read and contents stored in a hashMap by 'ZipFileReader'.The size of hashmap is now 2, containing bytes[] of a.txt and b.png

'write()' method takes bytes[] array and name of the file entry to be written to t he Zip file.

Each entry is closed by calling ZipOutputStream#closeEntry() method. Once closeEntry() is called , ZipOutputStream is ready for addition of a new Zip Entry.

Finally ZipOutpurStream#close() method is called. This method finally closes the stream
If the program misses to call 'close()' then a fautly zip file is written to the file system, that is corrupt and perhaps cannot be used. ZipOutpurStream#close() adds the required stream terminating characters.


import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.zip.ZipEntry;
import java.util.zip.ZipOutputStream;


public class ZipFileWriter {

    private String zipDir;
   
    private String zipFilename; // ends in .zip
   
    private static String FS = System.getProperty("file.separator" );
   
    public ZipFileWriter( String zipDir, String zipFilename ) {
        this.zipDir = zipDir;
        this.zipFilename = zipFilename;
    }
   
    /**
    }
     *
     * @return
     * @throws IOException
     */
    public void writeAsZip( byte[] bytesRead, String fileEntry ) throws IOException {

        String absoluteZipFIleName = zipDir + FS + zipFilename;
        ZipOutputStream zos = new ZipOutputStream(new FileOutputStream(absoluteZipFIleName));
   
        ZipEntry entry = new ZipEntry( fileEntry );
        zos.putNextEntry( entry );
       
        zos.write(bytesRead);
       
        zos.closeEntry();       
        zos.close();
    }
   
    public void writeAsText( String filename, byte[] bytesRead ) throws IOException{
        FileOutputStream fos = new FileOutputStream( new File( zipDir +  FS + filename ));
        fos.write( bytesRead );
        fos.close();
    }


 public static void main(String[] args) throws Exception {
     String FS = System.getProperty("file.separator" );
      String zipDirRead = "D:\\test";
      String zipDirWrite = "D:\\test\\out";
      String zipFilename = "cb-1-zip.zip";
     
      
      File zipFile = new File ( zipDirRead + FS + zipFilename );
     
      ZipFileReader reader = new ZipFileReader( zipFile );
      Map map = reader.read();
   
      ZipFileWriter writer = new ZipFileWriter(zipDirWrite, zipFilename);
      Set set = map.keySet();
      Iterator iter = set.iterator();
      while ( iter.hasNext() ) {
         
         String key = iter.next();
          System.out.println("Writing file Entry :" + key );
          byte[] bytesread = map.get(key);
       
          writer.writeAsZip( bytesread, key );
          writer.writeAsText( key, bytesread );
      }
   
}

Simple Java Program to Read Zip Files


This program takes a Zip File Name as input ( filename matchin regex '*.zip' )
'read()' method opens a ZipFileInputStream and reads each ZipEntry. A zipEntry is a file constituent of a zipFile. for E.g : if a zipFile name = =myzip.zip contains three files, namely :
file1.txt, file2.png, file.java, then myzip.zip has three ZipEntries.

Bytes contents of each Entry is written to a ByteArrayOutput stream and saved in a HashMap.
ZipInputStream and ByteArrayOutput streams are then closed


import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.zip.ZipEntry;
import java.util.zip.ZipInputStream;

public class ZipFileReader {

    private File zipFile;
   
    public ZipFileReader( File zipFile ) {
        this.zipFile = zipFile;
    }

    /**
     *
     * @return
     * @throws IOException
     */
    public Map read( ) throws IOException {

        ZipInputStream zis = new ZipInputStream(new FileInputStream(zipFile));
        Map byteMap = new HashMap();
       
        byte[] buffer = new byte[4096];
        ZipEntry entry = null;
   
        while ((entry = zis.getNextEntry()) != null) {
           
            ByteArrayOutputStream bos = new ByteArrayOutputStream();

            System.out.println("Extracting: " + entry);
            int numBytes;
   
            while ((numBytes = zis.read(buffer, 0, buffer.length)) != -1)
                bos.write(buffer, 0, numBytes);

            zis.closeEntry();

bos.close();
                       
            byteMap.put( entry.getName(), bos.toByteArray() );
            }
        return byteMap;
    }
   
  }

Wednesday, February 8, 2012

Back tracking procedure to find the exit through a maze

Here's a backtracking program to find the exit through a maze.
Maze is denoted by a 2D matrix with elements 0 and 1.
0 denotes a 'way ahead into the maze' and '1 denotes a blockage'
Let the matrix be :
static int[][] maze = new int[][] {
{ 0,0,0,0,1,0,0,0 },
{ 0,1,1,0,1,0,1,1 },
{ 0,1,1,0,1,0,0,1 },
{ 0,1,0,0,1,1,0,1 },
{ 0,1,0,0,0,1,0,1 },
{ 0,1,0,1,0,1,0,1 },
{ 0,1,0,0,0,1,0,1 },
{ 1,1,1,0,1,0,0,1 },
{ 1,1,1,0,0,0,1,1 }
};

Traversal steps :
1. Visit a particular index with value=0
2. Look in all the four directions to find out the all the valid directions in which a further movement can be made
3.Store all the current valid directions.
4. Make a movement into one these.
5. If arrived to the exit , then quit
6. Else move back and try other of stored directions

The procedure is recursive and current valid directions are stored on a stack.

Pathtoexit is the final matrix that denotes the correct path traversed to get to the exit;
Program output :
###############################
printing the co-ordinates of the right path
Success : x=0 y=7
Success : x=0 y=6
Success : x=0 y=5
Success : x=1 y=5
Success : x=2 y=5
Success : x=2 y=6
Success : x=2 y=7
Success : x=3 y=7
Success : x=4 y=7
Success : x=4 y=6
Success : x=5 y=6
Success : x=6 y=6
Success : x=7 y=6
Success : x=7 y=5
Success : x=8 y=5
Success : x=8 y=4
Success : x=8 y=3
Success : x=7 y=3
Success : x=6 y=3
Success : x=6 y=4
Success : x=5 y=4
Success : x=4 y=4
Success : x=4 y=3
Success : x=3 y=3
Success : x=2 y=3
Success : x=1 y=3
Success : x=0 y=3
Success : x=0 y=2
Success : x=0 y=1
----Input maze, 0=way ahead, 1=blockage------
0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 1
0 1 1 0 1 0 0 0
0 1 0 0 1 1 1 0
0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 1
0 1 0 0 0 1 0 1
1 1 1 0 1 0 0 1
1 1 1 0 0 0 1 1

---Exit path. 0 denotes the path to exit ------

0 0 0 0 1 0 0 0
1 1 1 0 1 0 1 1
1 1 1 0 1 0 0 0
1 1 1 0 1 1 1 0
1 1 1 0 0 1 0 0
1 1 1 1 0 1 0 1
1 1 1 0 0 1 0 1
1 1 1 0 1 0 0 1
1 1 1 0 0 0 1 1

######
----Below is the actual java code ----


/**
*
* @author Nitesh
*
*/
public class BackTrackingMaze {

public static void main( String[] args ) {
BackTrackingMaze bm = new BackTrackingMaze();
System.out.println("printing the co-ordinates of the right path");
bm.move( 0, 0, maze, -1, -1 );

System.out.println("-----------------Input maze, 0=way ahead, 1=blockage------------------");
bm.printInputMaze();

System.out.println("\n----------------- 0 denotes the path to exit --------------------- \n");
bm.printExitPath();
}

static int[][] maze = new int[][] {
{ 0,0,0,0,1,0,0,0 },
{ 0,1,1,0,1,0,1,1 },
{ 0,1,1,0,1,0,0,0 },
{ 0,1,0,0,1,1,1,0 },
{ 0,1,0,0,0,1,0,0 },
{ 0,1,0,1,0,1,0,1 },
{ 0,1,0,0,0,1,0,1 },
{ 1,1,1,0,1,0,0,1 },
{ 1,1,1,0,0,0,1,1 }
};

static int startX = 0;
static int startY = 0;
static int endX = 0;
static int endY = maze[ 0].length - 1;

static int[][] pathtoexit = new int[ maze.length ][ maze[0].length ];

static {
for ( int i = 0; i < maze.length; i++ ) {
for ( int j = 0; j < maze[i].length; j++ ) {
//pathtoexit[i][j] = maze[i][j];
pathtoexit[i][j] = 1;
}
}
pathtoexit[ startX ][ startY ] = 0;
}



int[] exitIndex = new int[] { endX, endY };

private boolean success = false;

private int dead_end = 2;
private int found_exit = 0;
private int dead_end_maze = 3;

private boolean isFreedom( int x, int y, int[][] maze) {
        //return (x == exitIndex[0] && y == exitIndex[1]);
        return ( y == maze[0].length-1 ) && ( maze[x][y] == 0 );
    }

    /**
     *
     * @param x, current x co-ordinate  into  this direction ( downward for the input matrix ) .... equivalent to lookSoth
     *                                                  |
     *                                                  |
     *                                                  |
     *                                                 \/
     *                                               
     * @param y, current y ordinate, into -----------> this direction ( horizontal direction ) .... equivalen to lookEast
     * @param maze
     * @param px
     * @param py
     * @return
     */public int move( int x, int y, int[][] maze, int px, int py ) {

if ( isFreedom ( x, y, maze ))
            success = true;

if ( success ) { return found_exit; }

// there are more valid moves
Stack stk = new Stack();
//x = row index
// y= column index

int[] north = lookNorth( x, y, maze, px, py );
if ( north != null ) stk.push( north );

int[] west = lookWest( x, y, maze, px, py );
if ( west != null ) stk.push( west );

int[] south = lookSouth( x, y, maze, px, py );
if ( south != null ) stk.push( south );

int[] east = lookEast( x, y, maze, px, py );
if ( east != null ) stk.push( east );

if ( stk.isEmpty() ) {
System.out.println( "dead end : row=" + x + " col=" + y );
return dead_end;
}
int[] out = null;
while ( !success && !stk.isEmpty() ) {
out = stk.pop();
int ret = move( out[0], out[1], maze, x, y );
if ( ret == dead_end ) {
System.out.println( "dead end returned: row=" + x + " col=" + y );
}
}

if ( success ) {
System.out.println("Success :" + " x=" + out[0] + " y=" + out[1]);
pathtoexit[ out[0] ][ out[1] ] = 0;
return found_exit;
}

System.err.println("Dead end maze, last index: " + " x=" + out[0] + " y=" + out[1] );
return dead_end_maze;

}

public int[] lookEast( int x, int y, int[][] maze, int px, int py ) {
int k = ++y;
return ( k == py || k == maze[0].length || maze[x][k] == 1 ) ? null : new int[] { x, k };
}

public int[] lookSouth( int x, int y, int[][] maze, int px, int py ) {
int k = ++x;
return ( k == px || k == maze.length || maze[k][y] == 1 ) ? null : new int[] { k, y };
}

public int[] lookNorth( int x, int y, int[][] maze, int px, int py ) {
int k = --x;
return ( k == px || k == -1 || maze[k][y] == 1 ) ? null : new int[] { k, y };
}

public int[] lookWest( int x, int y, int[][] maze, int px, int py ) {
int k = --y;
return ( k == py || k == -1 || maze[x][k] == 1 ) ? null : new int[] { x, k };
}

private void printExitPath() {
for ( int i = 0; i < pathtoexit.length; i++ ) {
for ( int j = 0; j < pathtoexit[i].length; j++ ) {
System.out.print( pathtoexit[i][j] + " " );
}
System.out.println("");
}

}

private void printInputMaze() {
for ( int i = 0; i < maze.length; i++ ) {
for ( int j = 0; j < maze[i].length; j++ ) {
System.out.print( maze[i][j] + " " );
}
System.out.println("");
}

}


}

Tuesday, January 31, 2012

InMemory Transpose of a sqaure matrix

/* swap every row with the corresponding column-- Let this step be called exchange
* After every exchange operation , size of matrix decreases by 1.
So further exchanges are to be made on this new reduced matrix.
So let suppose a 5 x 5 matrix, whose transpose we need to find
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

After first exchange( swapping values of row 0 with column 0 )
1 6 11 16 21
2 7 8 9 10
3 12 13 14 15
4 17 18 19 20
5 22 23 24 25

So the reduced matrix upon with subsequent exchanges are to made is a 4 x 4

7 8 9 10
12 13 14 15
17 18 19 20
22 23 24 25

Hence, the exchange Method has a loop 'for ( int k = i + 1; k < len; k++ ) {'

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}


**
*/

###### Complete Code #############################

public class TransposeOfMatrixInMemory {

public static void main( String[] args ) {
int[][] in1 = new int [][] {
{ 1, 2, 3, 4, 5 } ,
{ 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 },
{16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 }

};
TransposeOfMatrixInMemory obj = new TransposeOfMatrixInMemory();
int[][] in = obj.transpose( in1 ) ;
for ( int i = 0 ;i < in.length; i++ ) {
for ( int j = 0; j < in[i].length ; j ++ ) {
System.out.print( in[i][j] + " " );
}
System.out.println();
}

}

/**
* Matrix is a square matrix
* @param in
* @return
*/
public int[][] transpose( int[][] in ) {
if ( in == null || in.length == 0 ) return null;

int [][] tmp = in;


int len = tmp.length;
for ( int i = 0; i < len; i++ ) {
tmp = interchange( i, in );
}
return tmp;
}

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}



}

Friday, January 20, 2012

program to Unzip a file

/**
* This Unzip Unzips a zippedfile and returns the list of filesname unzipped
* @author Nitesh
*
*/
public class Unzip {

public static void main(String[] args) {
String dir = "E:\\data\\ad";
String zipFile = "zip.zip";
try{

Unzip list = new Unzip( );
List files = getUnZippedFile( dir, zipFile );
System.out.println("Unzipped file : ----------------");
for( File f : files ) {
System.out.println( f.getAbsolutePath() );
}
}
catch (Exception e)
{
e.printStackTrace();
}
}

/**
* Unzip all the files of the for 'zipfilename'. New folder created with the same name all the inner files
* written to the folder under the 'dir' directory
* @param dir
* @param zipFileName
* @return
*/
public static List getUnZippedFile(String dir, String zipFileName ) {

if ( dir == null || dir.length() == 0 || zipFileName == null || zipFileName.length() == 0 ) {
System.out.println("Cannot unzip. No Zip files found at location at directory : " + dir + " , filename :" + zipFileName );
return null;
}
if ( ! zipFileName.endsWith( ".zip") ) {
System.out.println("Unzipping fails. This file does not seem to be a ZipFile : " + zipFileName );
return null;
}
List unzipedFiles = null;
try {

File f = new File( dir, zipFileName );

byte[] buf = new byte[1024];
ZipInputStream zipinputstream = null;
ZipEntry zipentry;
zipinputstream = new ZipInputStream(
new FileInputStream( f ));

zipentry = zipinputstream.getNextEntry();
unzipedFiles = new ArrayList();

while (zipentry != null) {
//for each entry to be extracted
/* if the zip folder is test.zip and has file atest.csv then entryName = test/atest.csv */
String entryName = zipentry.getName();
System.out.println("entryname "+entryName);
int n;
FileOutputStream fileoutputstream;
File newFile = new File( entryName );
String innerZipFile = newFile.getName(); // e.g atest.csv

String parent = newFile.getParent(); // this determines if it is a folder zip or a file zip ??? strange , yep !
File ff = null;
if ( parent == null ) {
// This is the case of file zip. create a folder with the same name as 'zipfileName'
ff = new File( dir, zipFileName.substring(0, zipFileName.lastIndexOf("." ) ) );
}else {
ff = new File( dir, newFile.getParent() ); // create folder dir + test
}

if ( ! ff.exists() ) {
ff.mkdir() ;
}
File outputFile = new File( ff, innerZipFile );
fileoutputstream = new FileOutputStream( outputFile );

while ((n = zipinputstream.read(buf, 0, 1024)) > -1) {
fileoutputstream.write(buf, 0, n);
}

fileoutputstream.close();
zipinputstream.closeEntry();

unzipedFiles.add( outputFile );

zipentry = zipinputstream.getNextEntry();

}//while

zipinputstream.close();
}
catch (Exception e)
{
e.printStackTrace();
}
return unzipedFiles;
}
}

Monday, January 16, 2012

Print continuous longest substring without repeting chars from a charcter array

Longest consecutive substring without repetition


To find the longest substring without repetition of characters from an array of characters.
Let's suppose the string is "helloforhellowhy"
There are 1 continuous substring, with maximum length, without char repetition
"forhel" -- length =6

Another Example String: "nevertheless"  
 Maximum length without repetition: "verth" -- length = 5

String : aback
output: back -- length = 4

Belwo program prints the first string. It can be modified a bit to print all the possible substrings with maximum length



--------------------------------------------------------------------------------------

public class LongestSubstring {

    public static int[] longestWithoutRepeat(char[] input) {
        if (input == null || input.length == 0)
            return null;
        HashMap map = new HashMap<>(input.length);

        int[] lastIndices = new int[] { 0, 0 };
        int[] currentIndices = new int[] { 0, 0 };
        map.put(Character.valueOf(input[0]), 0);

        int j = input.length;
        int i = 1;

        while (i < j) {
            char c = input[i];
            Integer matchingCharIndex = null;

            if ((matchingCharIndex = map.get(Character.valueOf(c))) != null) {
                map.clear();
                updateLastIndices(lastIndices, currentIndices);
                currentIndices[0] = currentIndices[1] = matchingCharIndex.intValue() + 1;
                i = currentIndices[1];
                continue;
            }
            map.put(Character.valueOf(c), i);
            currentIndices[1] = i++;
        }
        updateLastIndices(lastIndices, currentIndices);
        return lastIndices;
    }

    private static int[] updateLastIndices(int[] lastIndices,
            int[] currentIndices) {
        if ((currentIndices[1] - currentIndices[0]) > (lastIndices[1] - lastIndices[0])) {
            lastIndices[1] = currentIndices[1];
            lastIndices[0] = currentIndices[0];
        }
        return lastIndices;
    }

    private static void print(char[] input, int[] lastIndices) {
        System.out.println("Greatest len = "
                + (lastIndices[1] - lastIndices[0] + 1));
        for (int m = lastIndices[0]; m <= lastIndices[1]; m++) {
            System.out.print(input[m]);
        }
    }

    public static void main(String[] args) {

        String test = "helloforhellowhy"; // forhel, 6 passed
        String test0 = "hellofaorhellowhyasmn"; // lowhyasmn 9, passed
        String test1 = "neverthaless"; // verthal 7, passed
        String test2 = "eee"; // e, paseed
        String test3 = "heeeeiop"; // eiop, passed
        String test4 = "343jbb6n78opnei"; // b6n78op7
        String test5 = "abcabcde";
        String test6 = "aback";
        String test7 = "hellofa";
        String test8 = "abcdefcghfa"; // abcdef 6
        String test9 = "abadbg";
        String test10 = "abakk";
       
        String input = test10;
        System.out.println("Input array = " + input + " ,Length="
                + input.length());
        int[] lastIndices = longestWithoutRepeat(input.toCharArray());

        print(input.toCharArray(), lastIndices);
    }
}

Tuesday, January 3, 2012

In a non-Empty binary tree Number of nodes of degree two is one less than number of leaf nodes

In a non-Empty binary tree
I.e a binary tree where every node has 2 child nodes or 0 child nodes
or a binary tree where every node has a degree 2 or is a leaf node

To prove : Number of nodes of degree two is one greater than number of leaf nodes
let n0 = no of leaf nodes
n1 = no of nodes with degree 2

then to prove that :
n0 = n1 + 1


Lets go about solving this problem with a simple imagination
Let assume a healthy binary tree to be one where each node is just healthy enough to give rise to 2 other nodes.
But due to some environmental complications, the tree gets diseased or little mutated i.e now every node either give rise to 2 nodes or none at all. So it's kind of saying that the nodes have now developed a flip-flop diseased nature.

Proof:
Let Nd denote nodes having dual nature, I.e which replicate into 2
Let Ns denote nodes having singular nature, I.e nodes which do not replicate at all

Let Kth level of tree has N1 dual nature nodes

So k+1 th level number of healthy nodes = 2*N1
but since the tree is diseased so
k+1 th level has nodes = ( 2*N1 – a1 ) + a1

where a1 is the nodes of nodes got diseased, So incapable of any further reproduction into duality

At level = k + 2
number of healthy nodes = 2 * ( 2N1 – a1 )
= 4*N1 – 2a1
but the tree is non-healthy so say b1 nodes again get diseased
so k+2 level nodes can be written as

k+2 has nodes = (4N1 – 2 a1 – b1 ) + b1
where b1 is the latest number of nodes to have got diseased, So incapable of any further reproduction into duality.

Extending the same logic at next level
At level = k + 3
number of healthy nodes = 2 * ( 4N1 – 2a1 – b1 )
= 8N1 – 4a1 -2b1

but the tree is non-healthy so, say, c1 nodes again get diseased
so k+3 level nodes can be written as
k + 3 has nodes = ( 8N1 – 4a1 – 2b1 – c1 ) + c1

Now let's take a break and find out how many leaf nodes and dual-nodes are present between Level=k and level=k+3

All the nodes at k+3 are leaf nodes
leaf nodes at level k+1 = a1
leaf nodes at level k+2 = b1
so total leaf nodes = 8N1 – 4a1 – 2b1 + a1 + b1
= 8N1 – 3a1 – b1

so Ns = 8N1 – 3a1 – b1

Now lets find out the total number of dual-nodes
level k+3 = 0
level k+2 = 4N1 – 2a1 – b1
level k+1 = 2N1 – a1
level k = N1

so total dual nodes = 7N1 – 3a1 – b1
so Nd = 7N1 – 3a1 – b1

Clearly Ns = Nd + 1

So number of leaf nodes is one greater than number of dual-nodes.

We stopped at level k + 3..... The same logic can be extended to fictitious infinite level binary tree

Monday, January 2, 2012

To Find the a subsequence of number having maximum sum in an array of numbers with positive negative values

Lets know the boundary conditions of the problem first

case 1:
If in negative plane:
conditions :
a. ) If the sum is negative.
keep treack of 2 variables :
1. downfall index ( index at which downfall started from a postive, i.e if the sum is negative )
2. upward index ( index at which upward movement began. i.e just check if the next number is postive )
if upward movement then sum=a[upwardindex]

case 2:
If in positive plane
keep adding as long the sum is positive

Case 3: Analysing transition periods

1. transition from positive plane to negative plane
sum till now of postive plane needs to stored as last_postive_sum

as long we keep moving in the negative plane there is no point in updating this last sum
as it can never increase with negative numbers.

2. But as soon as a trnasition again occurs from negative to positive i.e as sooon as a positive number is found
then new sum is the this found

3. At what time should we compare current_positive_sum and last_positive_sum
a. When a transition occurs from postive plane to negative. i.e when the downindex is freshly updated
then if current_postive_sum > last_positive_sum
then last_positive_Sum = current_positive_sum

4. The whole problem should be analysed by making a graph with y-axis, extending both in neg and posittive directions
values of y-axis are the array values
X-axis is the index of the array



/**
* @author Nitesh
*/
public class MaxSumInArray {

public static int maxSum( int[] in ) {
if ( in.length == 1 ) {
return in[0];
}
int negativeMax = in[0];
boolean notfound = true;
int i = 0;
for ( i = 1; i < in.length; i++ ) {

if ( in[i] < 0 && notfound ) {
if ( in[i] > negativeMax ) negativeMax = in[i];
continue;
}
notfound = false;
break;

}

if ( notfound && in[0] < 0 ) {
System.out.println( "all number are negative. Returning min negative");
return negativeMax;
}
if ( in[0] >= 0 ) {
i = 0;
}
System.out.println("Got the first postitive index :" + i + " , number=" + in[i] );

int current_max = in[i];
int last_max = current_max;
int downfall_index = -1;
int upward_iundex = -1;

for ( int j = i+1; j < in.length ; j++ ) {

/* first check the transition from negative plane to postive plane *
* in that case
* conditions :
* downward_index > -1
* and a[j] > 0
*/
if ( in[j] >= 0 && downfall_index > -1 ) {
downfall_index = -1;
current_max = in[j];
if ( current_max > last_max ) {
last_max = current_max;
}
continue;
}


/*
* If already moving in the negative plane then no need
* to update any pointer, either current_max, last_max, or any index
* condition :
* downward_index > -1
* and
* in[j] < 0
*/
if ( in[j] < 0 && downfall_index > -1 ) {
continue;
}

int t = current_max;
current_max += in[j];

/**
* If in positive plane then just update last max
* and continue
*/
if ( current_max >= 0 ) {
if ( current_max > last_max ) last_max = current_max;
continue;
}


/*
* if transition from positive plane to negative plane, i.e new_sum < 0 ?
*/

assert (current_max < 0 && downfall_index == -1);

if ( current_max < 0 && downfall_index == -1 ) {
downfall_index = j;
// now update last_max, i.e current_max might now be last_max
if ( t > last_max ) last_max = t;

}else {
System.out.println("Something wrong in ALGO ");
}

}

return last_max;
}

public static void main( String[] args ) {
int in[] = { 15,10, -3, -4, -5 }; // 25 ok ... pos, neg

int in1[] = { -3,-1,-22, -3, -4, -5 }; // -1 ok .... only negative

int in2[] = { 10, 13, -4, -6, 22, 1, -17, -19, 2 }; // 36 ok.. pos, neg, pos..

int in3[] = { 6,-11,-10,5 }; // 6 ok... pos, negative plane, positive plane

int max = maxSum( in3 );
System.out.println( "max=" + max );
}

}