Ryan Harrison My blog, portfolio and technology related ramblings

Maximum Sum Subsequence

The maximum sum subsequence of an array is the consecutive group of numbers that have the largest sum.

For example with the array {1, 11, -9, -20, 7, 10, -6, 3, 4, -2}, the maximum sum subsequence is 18 using the elements {7, 10, -6, 3, 4} starting from index 4 and ending at index 8.

Here are a few algorithms implemented in Java of increasing efficiency that can be used to solve this problem.

1. Brute Force -; take each element as a starting point and each element after as an ending point, sum the elements in between and keep track of the largest sum.

Efficiency (Order of Growth) = O(n^3)

 
// Calculate the maximum sum of a subsequence of an array  
// Returns an array containing the start index, end index and maximum sum  
// This algorithm has an order of O(n^3)  
public static int[] maximumSumSubsequence(int[] values) {  
	int max = 0;  
	int start = 0;  
	int finish = 0;

	for(int i = 0; i < values.length; i++) { 
		for(int j = i; j < values.length; j++) { 
			int sum = sumSequence(values, i, j); 
			if(sum > max) {  
				max = sum;
				start = i;  
				finish = j;  
			}  
		}  
	}

	return new int[] { start, finish, max };  
}

// Returns the sum of the elements of an array from start to finish inclusive  
private static int sumSequence(int[] values, int start, int finish) {  
	int sum = 0;  
	for(int i = start; i <= finish; i++) { 
		sum += values[i]; 
	} 
	return sum; 
}

Although this works well, it scales extremely badly with the algorithm taking nearly half a second with only 2000 elements. As the size of the input doubles, the time taken will increase by a factor of 8 - not good.

2. Remember the current sum. Instead of computing the sum of elements i to j on each iteration of the innermost loop, we can instead remember the current sum of the elements. This increases the efficiency by a factor of O(n).

Efficiency (Order of Growth) = O(n^2)

// Calculate the maximum sum of a subsequence of an array 
// Returns an array containing the start index, end index and maximum sum 
// This algorithm has an order of O(n^2) 
public static int[] maximumSumSubsequence(int[] values) { 
	int max = 0; 
	int start = 0; 
	int finish = 0; 
	for(int i = 0; i < values.length; i++) { 
		// now we remember the current sum on each iteration of the inner loop 
		int sum = 0; 
		for(int j = i; j < values.length; j++) { 
			sum += values[j]; 
			if(sum > max) {  
				max = sum;  
				start = i;  
				finish = j;  
			}  
		}  
	}
	return new int[] { start, finish, max };  
}  

This optimisation, although small saves a lot of execution time. Now as the size of the input array doubles, the time taken will increase by a factor of 4. However we can still improve this and gain a linear relationship between size and execution time.

3. Single loop -; now we only traverse the array once. We keep track of the maximal sum subsequence so far and the maximal sum subsequence ending at the current position.

Efficiency (Order of Growth) = O(n)

 
// Calculate the maximum sum of a subsequence of an array  
// Returns an array containing the start index, end index and maximum sum  
// This algorithm has an order of O(n)  
public static int[] maximumSumSubsequence(int[] values) {  
	int max = 0;  
	int start = 0;  
	int finish = 0;

	int endStart = 0;  
	int endMax = 0;

	for(int i = 0; i < values.length; i++) { 
		endMax += values[i]; 
		if(endMax > max) {  
			max = endMax;  
			start = endStart;  
			finish = i;  
		}

		if(endMax < 0) { 
			endMax = 0; 
			endStart = i + 1;
		} 
	} 
	return new int[] { start, finish, max };
}

Now we have the best case scenario for this problem. We cannot get any better as in the worst case scenario each element of the array has to be looked at at least once. With the now linear order of growth as the size of the input doubles, the time taken also doubles.

Read More

Installed Visual Studio 2012

Today I decided to take the step and upgrade from Visual Studio 2012 Professional to Visual Studio 2012 Premium so that I could take advantage of some of the language updates in .Net 4.5 and also be able to produce applications for the Windows Store. It also seemed like a good move as I can now get the software for free with the MSDNAA (Dreamspark Premium) account from my university.

I would have done it sooner but I knew it would probably be a long and laborious process trying to uninstall every element of my previous Visual Studio 2010 to then install the newer versions for 2012. I was not wrong. I really wish Microsoft would provide a good uninstaller for Visual Studio. At the moment the main uninstaller gets rid of just the main application, not any of the other stuff that it installs with it. You therefore have to manually go through your control panel trying to find things that may have been installed from VS 2010 - which takes a long time considering that Windows uninstallers are not the quickest of things at the best of times.

When I was finally able to get rid of just about everything, the installation process for Visual Studio 2012 went through without a hitch (the same for which could not be said for 2010). The installer itself was also very nicely designed and seemed to me at least faster than for VS 2010.

Here are a few screenshots -

Installation

Installed

Start Page

I really like the look and feel of the new styled interface so far. However I may have to try and figure out a way of reverting back to the old non-capitalised versions of the menu items.

Read More

New GitHub Account

Upon my recent post on my transferral from SVN to Git, I’ve now signed myself for a GitHub account.

I’m now in the process of uploading some previous projects up to GitHub for safe keeping which no doubt will prove helpful at some point.

Additionally this will enable me to simply link to a repository on GitHub instead of hosting project zip files here on this blog. This will no doubt make it much easier to give updates on any new changes to the code.

You can find my account at http://github.com/raharrison

Read More

SVN to Git

Recently Ive taken the time to learn the Git version control system. Upon previously using SVN for version control, Git seems to be a lot more powerful and user friendly. But perhaps one of the best reasons to use Git is the wealth of choice in online repository services using Git compared to that of SVN.

One of the best and most popular is github.com which provides unlimited public git repositories for free. Not bad at all.

So far my experience with Git has been very positive. Much easier branching/merging than SVN and the online documentation and support is very good. It has provoked me into making the switch from SVN to Git, or moving on with the times as many would say. Well see how it goes.

I’m also going sign up for a GitHub account. Can’t go wrong with unlimited free repositories. Hopefully it will get me into the habit of pushing everything up to online repositories which no doubt will save me one day when I accidentally delete something important.

Read More

Visual Studio 11 Beta Released

A beta version of Visual Studio 11 has been released alongside the beta of .NET 4.5.

Download Link

In Visual Studio 11 the whole interface has been transformed to a monochrome effect that is a lot more pleasing to the eye for long periods than previous versions which barraged the user with layers of colourful and distracting icons.

Visual Studio 11 Start Menu

With the code view open, the main focus is rightly where it should be - on the code. Nothing else is stealing your attention.

Visual Studio 11 Code View

Some of the new features including Hubs, Pivots and multi - instancing are explained in the Visual Studio Blog.

Read More