Simple implementation for 6.11

#1

Hi,
I gone through the solution which is provided on site for java implementation, seems complicated compared which I wrote: am I missing something?

public static void findLongestIncreasingSubarray (int[] a){
        int start=0;
        int end=0;
        int tempStart = 0;
        for (int i=1; i < a.length; i++) {
            if (a[i] < a[i-1]){
                if ((i-tempStart) > (end-start+1)) {
                    start = tempStart;
                    end = i-1;
                }
                tempStart = i;
            }
        }
     


    if((a.length-tempStart) > (end-start+1)){
        start = tempStart;
        end = a.length-1;
    }
    System.out.println("Start, end : ("+start+", "+end+")");
}
0 Likes
#2

Hey Srinivas,

I think your algorithm is missing the skip part in the book. Basically your algorithm will run in O(n) time but the algorithm in the book is in fact faster than this. Please take a look of that, and let us know what you think. It is a hard problem for sure, and it actually bothers me long time ago when I encounter this problem during an interview.

Tsung-Hsien

0 Likes
#3

Hi Tsung,

Thanks for your response. I checked the algorithm and understood the part to skip unnecessary comparisons. I liked this book very much apart from Java implementations. I couldn’t understand the implementation of java code for any problem easily though I understand the algorithm in book unless I dig into, would have been better if you write more comments along with code. Here is my updated code for this problem :

public static void findLongestIncreasingSubarray(int[] a){
	int start=0;
	int end=0;
	int tempStart = 0;
	int subArrayLength = 1;

	for(int i=1; i<a.length; i++){
	    if(a[i] <= a[i-1]){
		if((i-tempStart) > subArrayLength){
			start = tempStart;
			end = i-1;
			subArrayLength = end-start+1;
		}
		tempStart = i;
		// check back  to skip unnecessary comparisons
		for(int j=i+subArrayLength; j<a.length&&j>tempStart; j--){
			if(a[j] <= a[j-1]){
				tempStart = j;
				i = i+subArrayLength;
			}
		}
	    }
	}
		
	if((a.length-tempStart) > subArrayLength){
		start = tempStart;
		end = a.length-1;
	}
	System.out.println("Start, end : ("+start+", "+end+")");
}

Thanks,
Srinivas.

0 Likes
#4

Hey Srinivas,

Thanks for your reply, and I have to say this problem is really hard and we should do more work to improve it for sure. Would you mind to send me an email (tsung.hsien.lee@gmail.com) about Java codes that confuses you such that I can take a look of that. We constantly improve those codes as you should see those changes in our github repository, and your comments will definite make it better.

Tsung-Hsien

0 Likes
#5

Thanks Tsung. Sure, will email you the code next time if I have trouble to understand.

Thanks,
Srinivas.

0 Likes