pragmatism

Passwordless scp with Python and pexpect

2010-03-18T21:58:00.000-07:00

I have to deal with a lot of Unix/Linux/BSD boxes at work. The problem with such large number of boxes is copying my config files and .ssh directory first time I use them. Many a times, for some new work, I need to configure multiple boxes. It's quite a pain to enter passwords and pass-phrases that many times.

So, I decided to automate this copying with python and pexpect.

The script is really simple. You invoke it as follows:



$ pyscp.py -s .ssh,.vimrc,.zshrc,.screenrc,.inputrc -t node1,node2,node3

It will copy .vimrc, .zshrc .. to mentioned nodes. The automation looks for prompts asking for passphrases or passwords. You just have to enter your passwords once. On all subsequent attempts, the cached passwords is reused.

Password-less access can be configured using ssh-agents as well but this approach is generalized for all the cases - ssh not configured for public key authentication, ssh configured for keys with/without passphrase, with/without agent.The code can be cleaned further and made more elegant but it does the job.

The beauty of node.js (Follow-up)

2010-02-09T23:54:00.000-08:00

In the last post, I presented a simple port forwarding solution using node.js. The solution was simple, elegant and scalable. I got a follow up from Jeremy Ashkenas presenting a solution in Coffee Script.

I have a personal preference for terse syntax, one of my reasons for liking Python and Clojure.

For a little background, the coffee script compiler translates the given program to javascript and then it would run on any platform where Javascript runs. I queried him about how long and how extensively he intends to support Coffee Script. I am copying his response verbatim.

"I would say that it's not very mature yet. Aspects of the language syntax have changed as recently as last week. That said, CoffeeScript compiles into vanilla JavaScript -- it's not a runtime, and it's not a binary compiler, so even if the language were to go away tomorrow, you'd still be left with a bunch of completely usable JavaScript.So while I'm not using it for any real-world projects, other people are, and I'm not too worried about their future viability. In the absolute worst case, they can always used the output JS, which is pretty-printed, with comments inline."

Though it would be bad to start using Coffee Script only to find it gone some day, the risks are small. It isn't a mature project yet but it shows promise and I, for one, would start using it in personal projects.

The beauty of node.js

2010-02-09T07:06:00.000-08:00

At work I came across a problem which needed ack remote file copying complete event. Most of the data comes on ftp and when the data arrives, some processing has to be done on it. The problem is to when to kick in the processing. If we do a cronjob approach, the cronjob processor can't know for sure if the new file has been pushed completely. inotify posix system call only tell you the status of the file viz. created, modified, read etc.

EDIT: inotify does allow you to listen for the write complete events. The flag to look for is IN_CLOSE_WRITE. I kinda missed this.

The fix we have at work is to change the ftpd itself. The ftpd writes to a unix named pipe when the transfer completer. The listener daemon is watching the named pipe for changes and kicks in the callback when a new entry is made.

This works but has a couple of issues.

Changing the ftp daemon itself means keeping up with the ftpd changes. If a new release of ftpd is to be deployed, the patch has to be applied.
The same patching needs to be done if we decide to support another service. If we decide to allow rsync, similar fix has to be done for rsync as well.

How we do at work isn't going to change because our push data is solely ftp. But given a chance to re-design it, I would simply write a port forwarding service. The port forwarding server would listen at a dummy ftp port incoming. When a connection is made to port incoming, it would open a client connection to real ftp server. It would forward the whole traffic and it's only job would be to trigger the callback when the ftp transfer completes.

This solution required writing some code. Out of box port forwarding solutions don't have the customization for listening to end of transfer. So, faced with a problem, I did what everyone does - googled it. I found two acceptable solutions in Python. I prefer to code much of my stuff in Python for some obvious and not-so-obvious reasons(coming soon - topic for some other inflammatory post).

One of the solutions was spawning threads:
Port forwarding using threads

And the other one was using asyncore module.
Port forwarding using asyncore

The solutions worked and looked good for my taste. But something seemed amiss. It looked like just too much work when all I want to do is to know when the communication completes. I looked around a while and coded this in node.js.

The solution works and is terse, concise and highly scalable(look at the node.js website for how and why). And above all, it's as simple as it gets.

The code itself is pretty simple. I create a server and install callbacks for it. On connect event, I create the client for real service. Client and servers listen for receive, and the callbacks just sends data from one socket to other. The server socket triggers the callback on receiving the eof.

For the example, I am forwarding port 7000 to port 22. When we run the code and do a ssh on port 7000, the traffic is correctly forwarded to sshd running on port 22.



node portfwd.js
ssh -p 7000 localhost

This solution can be extended(must be extended) to function as a fully fledged port forwarder. The configurations(which port to forward where) can be passed as JSON. And the services to which we are forwarding should be made inaccessible to the outer world. For example, sshd can be configured to listen only to loopback address. This is important otherwise we run the risk of circumventing port forwarding and not running the callback.

There is much that can be done in node.js. This is just the tip of the iceberg. Looks like Javascript is really on the rise.

Sharing code with github

2010-02-06T22:38:00.000-08:00

I have been using pastebin to share code for a long time. While reading through a couple of blogs, I saw that github gists allow to share code in a prettier manner.

So, I decided to solve a small problem to test the github gists. The problem I am solving is to find the equidex. Equidex can be best explained by an example. Consider the given array:

{-7, 1, 5, 2, -4, 3, 0}

Here, index 3 is an equidex as the sum of the elements before it (-7 + 1 + 5) is the same as sum of the elements after it (-4 + 3 + 0).

Here is the code to solve it.

Objects: Functional programming style

2009-12-07T12:05:00.000-08:00

Functional languages which don't have build in objects support can implement object oriented programming using closures. Closures help implement encapsulation and the inheritance can be achieved using composition. The members can be maintained as members in hash ref. The hash ref will be closed by a closure so that external modification can't be done directly on it. Here is a sample code implementing encapsulation, inheritance and polymorphism.

Employee class extends person. It uses composition to implement inheritance.

The dispatch subroutine is the helper for implementing inheritance and polymorphism. You can see that this trivial code implements many important OOP concepts.

K&R - timeless classic

2009-11-17T00:29:00.000-08:00

There is a recent(well, may be not too recent) trend geared towards becoming overnight programmers. Peter Norvig has commented about that.

Viewing a couple of discussions on the web, I see people saying that K&R is hard to follow and they would prefer something with more examples and elaborations. I would drop any iota of diplomacy here and would say if you can't follow K&R, you are hopeless and either continue to be a monkey coder or find an alternate career.

K&R is the ultimate example of concise, complete, practical technical writing. I believe it is one of the primary reasons behind C's popularity. Everytime I re-read the book, I learn something new. And I am not the only one who feels that way. The coverage is comprehensive and explanations are lucid. The specs at the back used to be the standard C specs for the first 10 years or so. The examples are real world complete programs. Exercises force you to stretch your mental abilities. Compared to it, the other C texts look like a joke(with a couple of exceptions).

I am seeing a rise in head-first series now-a-days. I have read a couple of them and I did find "Head First Java" enjoyable. But again, it's suited only to the beginners and someone with some programming experience won't be too happy with it.

K&R is something I am religious about and would protect it to death. If you believe I am being over zealous here, read the book cover to cover and try the exercises. If it doesn't give you a better understanding of C and programming as a whole, you really don't have the aptitude for programming.

Standard *nix utilities using Perl

2009-08-09T08:17:00.000-07:00

Lately, I have been working on Perl and though I am not a big fan of the language, it does come handy for a variety of tasks. One of the reasons I like to keep in touch with Perl is it can very easily be used as substitutes for various *nix utilities viz. grep, sed, awk, find etc.

But why would someone want to do that when you already have the standard utilities? Well, you might be used to do everything in Perl. Or you might be on windows where the shell utilities are either non-existing or leave much to be desired. MS does claim to change that with PowerShell but I haven't looked at it yet.

So, enough talk. Here goes my short list of handy Perl one liners.

1) grep
grep is one handy little utility which does a full text search on the specified files.

$ grep -n 'main' *.c
formatting.c:3:int main(void)
hello.c:4:int main(void)

It can be done with a Perl one liner by using regex.

$ perl -ne 'print "$ARGV: $.: $_" if /main/; close ARGV if eof;' *.c
formatting.c: 3: int main(void)
hello.c: 4: int main(void)

2) sed
'sed', the venerated stream editor, is mainly used for substitutions.
$ echo "Hello world" | sed -e 's/Hello/Hi/'
Hi world

The perl equivalent for the above would be:
$ echo "Hello world" | perl -pe 's#Hello#Hi#'
Hi world

Neat, huh!

3) awk
awk is generally used for parsing delimited input. This is what we would do to get the username field from /etc/passwd.
awk -F: '{print $1;}' /etc/passwd

The perl one liner for this one would be:
perl -F: -lane 'print $F[0];' /etc/passwd

4) find
find is trickiest of them all. There isn't a shortcut available for it. Though the standard module File::Find comes handy.

To find and print all "*.c" files under directory "/usr/src", the find command would be:
find /usr/src -name '*.c' -print

The Perl equivalent is:
$ perl -MFile::Find -e 'find(sub {print "$File::Find::name\n" if /\.c$/;}, "/usr/src")'

There are other utilities which can be done using Perl viz. sort, cut etc. But these 4 are the ones that I miss the most when I am not on *nix.

svn - diff between working copy and checked out copy

2009-04-20T22:57:00.000-07:00

svn diff fileName

Pretty trivial. But the problem is the unified diff output is not very readable. And if the differences are large, it makes it practically impossible to follow through(which actually won't happen if you check-in often and keep your working copy updated).

EDIT: A simple way to do it would to do:

vimdiff <(svn cat "$1") $1

where $1 is the name of the file. Back to the point. I would prefer the diff between the working copy and checked out copy presented in a visually comparable manner. I am not much into UI oriented programs. For me, most of the times, it isn't a feasible option as I work on remote machines. So, here goes a trivial script without error checking which allows me to visually compare working copy and checked out copy.

#!/bin/bash
name="$@"
svn="/path/to/svn"
# Backup working copy, revert to checked out copy, 
# do the diff and restore working copy
mv "${name}" "${name}.bak"
${svn} revert "${name}"
mv "${name}" "${name}.orig"
mv "${name}.bak" "${name}"
vim -d "${name}" "${name}.orig"
rm "${name}.orig"
exit 0

The script is trivial and self-explanatory. "vim -d" might be unfamiliar. It opens vim vertically split in two panes showing the two files highlighting the differences. Additions, deletions and modifications are color-coded making it easy for analysis. I find the diff mode in vim very useful for manual merging. I use it all the time to resolve conflicts during check-in.

Here is a quick refresher on vidiff:
]c - next difference
[c - previous difference
dp - put differences to other file
dg - get differences from other file

You will be surprised that how much is accomplished from these 4 commands.

Privacy using public key cryptography

2009-04-20T04:22:00.000-07:00

Incompetent governments around the world are coming out with oppressive measures to curb privacy of citizens in the name of controlling terror. Let's face it. How is being terrorized by the government different from terrorized by some other motherfucking moron? Secrecy is different from privacy. I won't enjoy even my daily joke forwards being forcefully read by government agencies.

The recent regulations require email hosting services to have their servers in India to bring them under Indian jurisdiction. God knows what purpose it can possibly server. At best, the details that were being submitted while creating the a/c can be extracted. And though the terrorists are a bunch of idiots, still, going by the best practices, they don't fill in their correct details. The mails are encrypted and government agencies neither have the know-how nor the resources to attempt a decryption. Theoretically every encryption algorithm is breakable and most of them depend on no efficient algorithm for factoring a large number into prime factors. Practically, anything beyond 64 bit would take like eternity to brute force. No known deterministic polynomial time algorithm exists.

Being lawful citizens, there isn't much we can do about mail servers moved to India and forced to divulge details available with them but we sure can encrypt our mails.

Some background

Secret/Private/Symmetric key cryptography

The same key (a kind of password which isn't limited to numbers, alphabets and special characters but can consist of any arbitrary byte sequence) is used for encryption and decryption.

It is kinda weak as you need to share your key with the other end. Further, if anyone gets hold of the key, he not only can decrypt the files but can send encrypted files which would appear to come from the other end(based on the belief that only the other end has got the key).

Public key cryptography
Everyone has a public and private key. Public key is published on a known forum and private key is just what it says - private. If user A wants to send an encrypted message to user B, he will encrypt it with B's public key which is accessible to anyone. A document encrypted with B's public key can only be decrypted by B's private key and vice-versa. This "vice-versa" has an interesting application - digital signatures. Not getting too involved, digital signatures are a way of testifying your identity. And unlike actual signatures, they can't be forged unless you loose your private key.

Enough theory. Let's see how this can be done using GnuPG(GNU Privacy Guard).

* Symmetric encryption



1 gpg -c filename
2 gpg -c -a filename

Both 1 and 2 will prompt for a password and then go on with encrypting the file. 1 produces binary output while 2 produces base-64 encoded output.

Decryption is simple



gpg encryptedFile

This will de-crypt the file in-place after prompting for and verifying the password.

Key generation for public key encryption
The keys are generated using:



gpg --gen-key

It will ask you a couple of questions. Defaults are OK if you don't understand them. A public/private key will be created after successful execution of this command.

Sharing public key
After generation of keys, you need to share it with others. For that, either you can export your keys and physically pass it along or you can upload it to any of the key servers. I have mine on pgp.mit.edu and it propagates it to a number of other keyservers. Here is how you export a key and upload it to a key server:



Exporting key:
gpg --export key_name
Sending keys to server:
gpg --keyserver serverName --send-keys keyID
Key id is obtained by seeing the listing:
gpg --list-keys

Importing keys
That is about giving your keys to others. When you receive keys from someone else, you need to import the keys in your keyring.



Receiving keys from a key-server:
gpg --keyserver serverName --recv-keys keyID
Importing physically received keys:
A "gpg keyfile" would import the keyfile into your keyring. But that's not it. Further steps are required.

First verify the key fingerprint:
gpg --fingerprint keyID
The fingerprint is the unique identifier for the key. People post it on the web, pass it on disks, verify over phone etc. 
Once the fingerprint has been verified, you can set the key as trusted.
gpg --edit-key keyID
command>trust

Grand finale
Phew! That sure was a lot of work and a lot of pain. But now you are done. Say now you need to send a file to A, all you need to do is



gpg -s -e -r keyIdForA file

This will:
1) encrypt your file in such a way that only A can decrypt it
2) Sign your file so that when it reaches A, A know that you have sent it. It also verifies that the file hasn't changed in the transit.

When A receives the file, all he has to do is:



gpg encryptedFile

Since the file was encrypted for him and assuming he has a default private key configured and your public keys in his keyring, this command will verify and decrypt the file.

Now go and enjoy your new-found privacy. Don't forget to spread word about importance of privacy.

What? You use M$ Windows? Get a life. Just kidding :-). Google for a windows version of GnuPG. Basically, any pgp or openssl or equivalent implementation will do the trick.

"private" in Java

2009-02-06T21:03:00.000-08:00

Some people take the concept of "private", "public" in OOP a little too seriously. That is meant to be a logical concept and that most certainly does not mean that private members can't be accessed. The debugger does that all the time. If "private" members were so inaccessible, then even the debugger shoudn't have been able to dump their values since the debugger is external to class being debugged. Reflection can be used to access the private members of a class. It depends on SecurityManager installed. The default SecurityManger allows accessing private members using reflection.

The reflection API does have methods for invoking private methods as well. These techniques are internally used by the debugger and can be used for debugging purposes.

Running a Java program without a main

2009-02-06T20:51:00.000-08:00

Java allows static initialization blocks which run before the class is loaded. Since the main method is contained in a class in Java, the static initialization block runs before main. Though running code through static initialization block would output a message about "main not found". This message can be avoided by ending the static initialization block with a System.exit(0).

The first Hello.java is the traditional "Hello World" program. Hello2.java prints "Hello World" without a main but the spits an error message about "main not found". Hello3.java print "Hello World" and then exits thus avoiding the error messsage.

Detecting cycle in a linked list

2009-02-06T09:40:00.000-08:00

Finding cycle in a linked list in a single pass is an often asked question. The first approach that people tend to do is to store the seen node pointers into an array. And everytime a new element is encountered, it is searched in the seen array. But that's very inefficient. An auxiliary array of size n is required. Further, for each element, a search into the array is to be made followed by the insertion.

This isn't actually required. A cycle in a link list can be detected by taking a fast and slow pointer. Everytime a slow pointer advances by one, fast advances by two. If at any point of time, fast becomes equal to slow, that indicates a cycle in the list.

Feel free to experiment that this work for all sort of cycles. This code returns 1 when passed a single element list.

Finding common ancestor of two given nodes in a binary tree

2009-02-05T08:42:00.000-08:00

Given two nodes n1 and n2, the problem is to find the common ancestor. The common ancestor depends on the relation between two nodes and the root.

1) If n1 is less than root and n2 is greater than root, then root is the common ancestor for the nodes.

2) If both nodes are smaller(or greater) than root, then call the algorithm recursively.

Recursively applying this algorithm to the tree will give the common ancestor.

If the two nodes lie on two sides of the ancestor, then the algorithm is straight forward. The special if conditional is required when the two nodes fall in the same linear path. In that case, the parent of the smaller (or larger) of two will be the common ancestor. Since there is no way to get to a node's parent, we pass the parent as a function parameter.

Google's real time search

2009-02-04T20:09:00.000-08:00

I am posting this on 9:43 AM IST. The sole purpose of this post is to test how quickly it starts appearing in search results. I have heard that it takes less than 10 seconds. Lets put the theory to test. I have got another google search page open with "rahulsinner google's real time search" as the search query.

/* Checked the search results */
So it turned out to be one of the urban legends. I didn't get anything related. But it was obvious from the beginning itself. Google's search to results latency is very small. What I mean is the lapse when Google's crawler hits a page and it starts appearing in results is very small. Google must be having some real time clusters which don't use a static db but are fed data on the run.

/* Checking back after 2 hours */
I don't know when it appeared on the search. Its 11.51 am. That is about 2 hours(or lesser - I checked the results just now).

Object oriented desing principles

2009-02-03T05:47:00.000-08:00

All complex talks and terms regarding object oriented analysis and design notwithstanding, there are only a couple of commonly used principles that if used wisely, can lead to extensible code.

Open/Closed principle
This principle says that the classes should be designed such that they are open for extension and closed for modification. Various other principles viz. access controOpen/Closed principlel - public, private, protected and programming to interface are a direct derivative of this principle.

The Connection class is open to extension but closed to modification.

Liskov Substitution Principle
This helps avoids simple design mistakes. Consider the following:

This design looks good as a Square is juat a rectangle which has length = breadth. But it fails the LSP. LSP says that a super class should be able to stand for the subclass(yes, you are reading it right). What possibly can getLength() and getBreadth() methods mean for the Square class? Since the superclass isn't sharing much behaviour with sub-class, this inheritance is flawed. The proper way to implement would be :

All the generic code should go into Shape and all the methods should be applicable to both Rectangle and Square.

Java, does a violation of LSP as the methods defined in Object don't do anything useful in their default implementation. As a rule, they need to be overridden. The proper design should have made Object an interface rather than a class.

Single Responsibility Principle - SRP
A class should be doing one thing. Cosider:

Well, a Person class shouldn't be connecting to DB. A helper class should be written. That way, you only change the helper class when you change the back-end db.

Don't Repeat Yourself(DRY)
If you find code being repeated, abstract the code into a separate module. That directly enhances usability. At the same time, the changes are less painful. Consider having a Person, Employee, Engineer classes. Each one of them have methods to store themselves to the DB. If you decide to change the backend db, you will have to change the code at 3 locations. In real life scenarios, the number is far, far larger than 3.

Watch your classes

Do you see something wrong with this class? This isn't a class at all. A class is both data and behaviour and the Person class above is just data. If you ever find yourself defining classes in this manner, re-think your desing. Either your class design is flawed or you don't need the class at all. You should be using a Hashmap if all that you are going to do is store name value pairs.

MySQL Replication Part 2

2009-02-02T20:58:00.000-08:00

This is a follow up of the previous post about MySQL replication.

Overview
The replication model involves one server as Master and one or more servers as Slaves. The slaves periodically update themselves with server. The keep track of the changes by following the binary log maintained by the Master.

Creating user
For security reasons, its always better to have a dedicated user for replication. This user account is used by slave to connect to master and get the data. So, we need to create a user on master.

First create the user on slave:



create user 'replica' identified by 'replica';

Then grant access on master.



grant replication slave, replication client

on *.*

to 'replica'@'slave_node'

identified by 'replica';

Changing my.cnf
Under linux, my.cnf is the file that needs to be changed to configure a node as a master/slave. The following goes under [mysqld] section:

 

server-id = 1

log-bin = /var/log/mysql/backup.log

The server id should be unique among the masters and slave. Other than that, there aren't any other constraints and it can be anything.

For the slave, the configs are more elaborate.



server-id = 2



master-host = mastersite.com

master-user = replica

master-password = replica



log-bin = /var/log/mysql/backup.log

log-bin-index = /var/log/mysql/log.index

log-error = /var/log/mysql/error.log



relay-log = /var/log/mysql/relay.log

relay-log-info-file = /var/log/mysql/log.info

relay-log-index = /var/log/mysql/relay-log.index

The first section defines the connection to the master. The second section starts binary logging on slave. The relay section makes a copy of master's binary log on the slave.

Initializing
Now we need to take a dump of existing data, dump it on slave, start the slave and we are done.

The following needs to be run on master node.



mysqldump --user=root --password=foo

--extended-insert --all-databases 

--master-data  > backup.sql

Then this dump is to be executed on slave node.



mysql --user=root --password=foo < backup.sql

That completes the configuration. We just need to start the slave and it will periodically sync itself with the master. In case of master, all it takes is switching the nodes based on some config or dns results.



mysql --user=root --password=foo

mysql> start slave;

MySQL replication

2009-02-02T20:39:00.000-08:00

MySQL is a robust, reliable and mature database server. Nevertheless, you can't expect it not to crash ever. That is why prouduction databases always have replicas. Off late, mysql has been supporting replication out of the box. You can choose either to use mysql's replication or implement a trivial replication mechanism.

Replication by hand
The strategy is simple. Write a cronjob which takes a snapshot of the database and rsyncs the snapshot to a fixed location. The rsyncing part can be replaced with commiting to svn(or other repository) as well.

A simple shell script can do this stuff.





#!/bin/bash



mysqldump --user=foo --password=bar --all-databases > /replica/backup-`date`.sql



# tables can be locked to avoid any inconsistencies. the downtime, if any, will depend on the #    size of the database.

# mysqldump --user=foo --password=bar --all-databases --lock-all-tables --extended-insert >     

# /replica/backup-`date`.sql

Having it on the same node won't do any good in case of disk failures. In that case, a better idea would be to rsync it to some other node or check it in the repository.





#!/bin/bash

# tables can be locked to avoid any inconsistencies. the downtime, if any, will depend on the #    size of the database.

file_name=backup-`date`.sql

mysqldump --user=foo --password=bar --all-databases --lock-all-tables --extended-insert >     

/replica/${file_name}

rsync /replica/${file_name} backup_node::backup

Extending the script to check it in the repository is straight forward.





#!/bin/bash

# tables can be locked to avoid any inconsistencies. the downtime, if any, will depend on the #    size of the database.

file_name=backup-`date`.sql

mysqldump --user=foo --password=bar --all-databases --lock-all-tables --extended-insert >     

/replica/${file_name}

cmd="cd /replica && svn commit -m 'automated db backup'"

${cmd}

if [ $? -ne 0 ]

then

echo "backup failed" 2>&1

fi

cmd="cd /replica && svn update"

${cmd}

if [ $? -ne 0 ]

then

echo "backup done and disk copy updated"

fi

Fiding duplicated element in an array

2009-02-02T06:16:00.001-08:00

A simple variation on the theme on finding the missing element is finding the duplicated element. Given a n sized array, 1 to n - 1 are there and one element is duplicated. The problem is to find the duplicated element in a single pass. Again, this problem breaks down to simply calculating the sum.

The sum of array = sum of n - 1 number + x (duplicated number)

The duplicated number is obtained by subtracting the sum of n - 1 numbers from the actual sum.

Finding missing element in an array

2009-02-02T06:03:00.000-08:00

This is a damn simple one if you remember your basic mathematics. The problem statement give an array of size n which consists of numbers from 1 to n + 1. The question is to find the missing number. Like given an array of size 5:



int a[5] = {1, 2, 5, 3, 4}

This 5 sized array has numbers from 1 to 6 and one number is missing. That number is to be calculated in a single pass. The sum of numbers from 1 to n is (n * (n + 1)) / 2. The sum of the given array is sum of n - 1 numbers plus one number that is repeated. So this is what we have.

Sum of n numbers = (n * (n + 1) ) / 2

Sum of the array = sum of n numbers - missing number

Its pretty straight forward to see that 1 -2 gives the missing number.

Calculating maximum sum ranges

2009-02-02T02:06:00.000-08:00

Someone asked me how would I calculate the maximum sum range in a given array. Like given an array
int a[] = {1, -30, 50, 10, -80, 8, 5, 15}

I was asked to calculate the start and end index which will have the highest sum. This really caught me off guard. I went as ahead as thinking that this isn't solvable in polynomial time. But in fact, its quite a straight forward question.

This is just about generating the ranges. Given an array of size n, the different ranges possible would be:
0-1, 0-2, 0-3 ... 0- (n-1)
1-2, 1-3, 1-4 ... 1 - (n-1)
...
(n-1) - n

Once you figure out this, its quite a straight forward question. We just have to calculate the sum for all the ranges and figure out which one is the highest. The question reduces to finding all the ranges, their sums and the maximum sum.