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 );
}

}

Find all the subsets of a given set

public class Subset {


public static List subset( List input ) {
double r = input.size();
int finalsize = (int)Math.pow( 2d, r );
List ret = new ArrayList( finalsize );
int one = 0x0001;
for ( int i = 1; i < finalsize; i++ ) {
int count = 0;
StringBuilder sb = new StringBuilder();
while ( count < finalsize ) {
int k = (i >> count) & one;
if ( k == 1 ) {
sb.append( input.get( count ) ).append(",");
}
count++;

}
ret.add( sb.toString() );
}
return ret;
}

public static void print( List in ) {
int i =1;
for ( String s : in ) {
System.out.println( "count_" + (i++) + " :" + s );
}
}

public static void main( String[] args ) {
List in = new ArrayList();
in.add( "a" );
in.add( "b" );
in.add( "c" );
in.add( "d" );
print ( subset( in) );
}
}

Find permutation of a String or character array

/**
* Finds premutation of an array of characters
* @author Nitesh
*
*/
public class Permutation {

public static void main( String[] args ) {
Permutation perm = new Permutation();
String s = "abcde";
char[] c = s.toCharArray();
char[][] ret = perm.permut( c , 0, c.length-1 );
perm.print( ret );
}


/**
* Begin = begin index
* end = end index
* input = char input
*
* @param input
* @param begin
* @param end
* @return
*/
public char[][] permut( char[] input, int begin, int end ) {

int len = end - begin + 1;
if (len == 1 ) {
char[][] ret = new char[1][];
ret[0] = input;
return ret;
}
if ( len == 2 ) {
char[][] ret = new char[2][];
ret[0] = input;
char[] a = copy( input );
a = swap( a , begin, end );
ret[1] = a;
return ret;
}
char pivot = input[begin];
int pivot_index = begin;
char[][] per = permut( input, begin+1, end );
return merge ( begin, per );

}

char[][] merge( int pivotIndex, char[][] input ) {
int rows = input.length;
int cols = input[0].length - pivotIndex;
int len = rows * cols;
char[][] ret = new char[len][];
for ( int i = 0; i < rows; i++ ) {
ret[i] = input[i];
}
int k = rows;
char[][] cir;
for ( int i = 0; i < rows; i++ ) {
cir = getCir( ret[i], pivotIndex );
for ( int j =0; j < cir.length; j++ ) {
ret[ k++ ] = cir[j];
}
}
return ret;

}

public void print( char[][] c ) {
for ( int i = 0; i< c.length; i ++ ) {
System.out.println( "count_" + (i+1) + "=" + new String( c[i] ) );
}
}

char[][] getCir( char[] c , int ele ) {
char[][] ret = new char[c.length -ele - 1][];

for ( int i = ele + 1, j=0; i < c.length; i++, j++ ) {
char[] cop = copy( c );
cop = swap( cop, ele, i );
ret[j] = cop;
}
return ret;
}

char[] copy( char[] input ) {
char[] ret = new char[ input.length ];
for ( int i = 0; i < input.length; i++ ) {
ret[i] = input[i];
}
return ret;
}

char[] swap( char[] a , int begin, int end ) {
char c = a[begin];
a[begin] = a [end];
a[end] = c;
return a;
}


}

Neko HTML Fragment Parser with Xml Transform

import java.io.ByteArrayInputStream;
import java.io.StringWriter;

import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerException;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;

import org.apache.html.dom.HTMLDocumentImpl;
import org.apache.xpath.XPathAPI;
import org.cyberneko.html.parsers.DOMFragmentParser;
import org.w3c.dom.DocumentFragment;
import org.w3c.dom.Node;
import org.w3c.dom.html.HTMLDocument;
import org.xml.sax.InputSource;

/**
*Working with html fragements and tranforming node result
*to xml string
*/
public class HtmlFragmentTest {

String exp = "//TABLE[@class=\"subscribe_form\"]";
String xml = null;


public HtmlFragmentTest() {

StringBuffer sb = new StringBuffer();

sb.append( "<h2>Contributing to the FAQ</h2>\n" + "<p>If you think that you have a FAQ that's not answered here, or if you\n" + "see something that needs a correction/update, please\n" + "<a href=\"/contribute/\">contribute</a>!</p>\n" );

sb.append( "<table class=\"subscribe_form\" cellpadding=\"0\" cellspacing=\"0\"><tr>\n");

sb.append( "<td class=\"label\">\n" );

sb.append( "To get updates by email whenever the FAQ is updated, enter your email"+ "address here and click "Subscribe:"\n" );

sb.append( "</td>\n" + "<td>\n" + "<form method=\"post\" action=\"/notify.php\">\n" );

sb.append( "<div>\n" + "<input type=\"text\" size=\"20\" name=\"email\" />\n" + "<input type=\"submit\" value=\"Subscribe\" />\n" + "</div>\n" );

sb.append( "</form>\n" + "</td>\n" + "</tr></table>");

xml = sb.toString();

}

public void test() {

HTMLDocument document = new HTMLDocumentImpl();
DocumentFragment doc;
try {

DOMFragmentParser parser = new DOMFragmentParser( );

//parser.setFeature("http://cyberneko.org/html/features/insert-namespaces", true);
parser.setFeature ( "http://xml.org/sax/features/namespaces", false );
parser.setProperty("http://cyberneko.org/html/properties/names/elems", "lower" ); // has no effect, cannot override xerces configuration
parser.setProperty( "http://cyberneko.org/html/properties/names/attrs", "lower" ); // has no effect, cannot override xerces configuration
parser.setFeature("http://cyberneko.org/html/features/balance-tags/document-fragment",true);

doc = document.createDocumentFragment();
InputSource inputSource = new InputSource( new ByteArrayInputStream( xml.getBytes() ) );

parser.parse(inputSource, doc);

Node node = XPathAPI.selectSingleNode(doc, exp);
this.xml = transform( node );
System.out.println( "---------------done once --------------");

} catch(Exception ex) {
ex.printStackTrace();
//return null;
}
}

public static void main( String[] args ) {
HtmlFragmentTest test = new HtmlFragmentTest();
test.test();
test.test();
}

/**
*
* @param node
* @return
* @throws TransformerException
*/
public static String transform( Node node ) throws TransformerException {
StringWriter sw = new StringWriter();
Transformer serializer = TransformerFactory.newInstance().newTransformer();
serializer.transform( new DOMSource( node ), new StreamResult(sw));
String result = sw.toString();
System.out.println( result );
return result;
}

}

Email attachment downloader

This simple java program uses java mail to connect to a pop mail server and reads inbox, iterates through the inbox messages and then downloads the message attachments if any.

Steps:
1. Make a session with aunthenticator
2. Get the Store and call store the connect.
3. Get the folder "INBOX" from the store and open it for read and write.
4. Read the attachement Part by part.getInputStream()
5. write the read bytes to the output file stream

Some properties values to be used:
a. user : name of the user on the email server like abc.kk@abcmail.com
b. password : user's passoword for authentication
c. protocol : pop3 or any other protocol for reading mails
d. attachment : directory location for attachment downloads




public void doEMailDownload( ) throws Exception {
// Create empty properties
// Properties props = new Properties();

Properties props = new Properties();

// Get the session
// Session session = Session.getInstance(props, null);
Session session = Session.getDefaultInstance(props,
new javax.mail.Authenticator() {
protected PasswordAuthentication getPasswordAuthentication() {
return new PasswordAuthentication( receiving_user, receiving_pass );
}
});

// Get the store
Store store = session.getStore(receiving_protocol);
store.connect(receiving_host, receiving_user, receiving_pass);

// Get folder
Folder folder = store.getFolder("INBOX");
folder.open(Folder.READ_WRITE);

try {

// Get directory listing
Message messages[] = folder.getMessages();
EmailPolicy emailPolicy = new EmailPolicy();

for (int i=0; i < messages.length; i++) {
// get the details of the message:
EMail email = new EMail();

email.subject = messages[i].getSubject();

/* filter Email Inbox as per some download policy */

if ( ! emailPolicy.checkAllPolicies( messages[i] ) ) {
continue;
}

email.fromaddr = messages[i].getFrom()[0].toString();
Address[] to = messages[i].getRecipients(Message.RecipientType.TO);
email.toaddr = "";
for(int j = 0; j < to.length; j++){
email.toaddr += to[j].toString() + "; ";
}
Address[] cc;
try {
cc = messages[i].getRecipients(Message.RecipientType.CC);
} catch (Exception e){
System.out.println("Exception retrieving CC addrs: %s" + e.getLocalizedMessage());
cc = null;
}
email.cc = "";
if(cc != null){
for(int j = 0; j < cc.length; j++){
email.cc += cc[j].toString() + "; ";
}
}
email.subject = messages[i].getSubject();
if(messages[i].getReceivedDate() != null){
email.received_when = messages[i].getReceivedDate().getTime();
} else {
email.received_when = new java.util.Date().getTime();
}


email.body = "";
Vector vema = new Vector();
Object content = messages[i].getContent();
if(content instanceof java.lang.String){
email.body = (String)content;
} else if(content instanceof Multipart){
Multipart mp = (Multipart)content;

for (int j=0; j < mp.getCount(); j++) {
Part part = mp.getBodyPart(j);

String disposition = part.getDisposition();

if (disposition == null) {
// Check if plain
MimeBodyPart mbp = (MimeBodyPart)part;
if (mbp.isMimeType("text/plain")) {

email.body += (String)mbp.getContent();
} else {
// Special non-attachment cases here of
// image/gif, text/html, ...
EMailAttach ema = new EMailAttach();
ema.name = decodeName(part.getFileName());

if ( ! isAllowedAttachment( ema.name ) ) continue;

File savedir = new File(receiving_attachments);
if ( savedir.exists() ) {
savedir.mkdirs();
}
//File savefile = File.createTempFile("emailattach", ".atch", savedir );
File savefile = new File( savedir, ema.name );
ema.path = savefile.getAbsolutePath();
ema.size = part.getSize();
vema.add(ema);
ema.size = saveFile(savefile, part);
}
} else if ((disposition != null) &&
(disposition.equals(Part.ATTACHMENT) || disposition.equals(Part.INLINE) )
){
// Check if plain
MimeBodyPart mbp = (MimeBodyPart)part;
if (mbp.isMimeType("text/plain")) {
System.out.println("Mime type is plain");
email.body += (String)mbp.getContent();
} else {
System.out.println("Save file (%s)" + part.getFileName() );
EMailAttach ema = new EMailAttach();
ema.name = decodeName(part.getFileName());
File savedir = new File(receiving_attachments);
savedir.mkdirs();
//File savefile = File.createTempFile("emailattach", ".atch", savedir );
File savefile = new File( savedir, ema.name );
ema.path = savefile.getAbsolutePath();
ema.size = part.getSize();
vema.add(ema);
ema.size = saveFile( savefile, part);
}
}
}
}


// Finally delete the message from the server.
//messages[i].setFlag(Flags.Flag.DELETED, true);
}

// Close connection
folder.close(true); // true tells the mail server to expunge deleted messages.
store.close();
} catch (Exception e){
folder.close(true); // true tells the mail server to expunge deleted messages.
store.close();
throw e;
}

}

public static class EMail {
public String fromaddr;
public String toaddr;
public String cc;
public String subject;
public long received_when;
public String body;
}

/**
*
*/
public static class EMailAttach {
public String name;
public String path;
public int size;
}

/**
*
* @param saveFile
* @param part
* @return
* @throws Exception
*/
protected int saveFile(File saveFile, Part part) throws Exception {

BufferedOutputStream bos = new BufferedOutputStream( new FileOutputStream(saveFile) );

byte[] buff = new byte[2048];
InputStream is = part.getInputStream();
int ret = 0, count = 0;
while( (ret = is.read(buff)) > 0 ){
bos.write(buff, 0, ret);
count += ret;
}
bos.close();
is.close();
return count;
}

protected String decodeName( String name ) throws Exception {
if(name == null || name.length() == 0){
return "unknown";
}
String ret = java.net.URLDecoder.decode( name, "UTF-8" );

// also check for a few other things in the string:
ret = ret.replaceAll("=\\?utf-8\\?q\\?", "");
ret = ret.replaceAll("\\?=", "");
ret = ret.replaceAll("=20", " ");

return ret;
}