CareerCup

Modified Kadane's algo will be O(N)

Kadane algorithm

def max_sum(seq):
    
    max_sum_= 0
    sum_ = 0
    for i in seq:
        if sum_ + i < 0:
            sum_ = 0
        else:
            sum_ += i
        
        max_sum_ = max(sum_, max_sum_)

    print "Max sum is {0}".format(max_sum_)

Modified for this problem:

def max_sum_sorted(seq_pairs):
    
    max_sum_= 0
    sum_ = 0
    
    # Initialize to the maximum negative integer
    prev_first = -sys.maxint
    
    for pair in seq_pairs:
        # first element has to be sorted
        first, second = pair
        
        if first < prev_first:
            sum_ = 0
    
        if sum_ + second < 0:
            sum_ = 0
        else:
            sum_ += second
    
        max_sum_ = max(sum_, max_sum_)
        prev_first = first

    print "Max sum is {0}".format(max_sum_)

If the subarray is contingous then you can go for Kadan's algorithm suggested by mindless monk. If you need to consider subsequence then dynamic programming approach, as the optimal substructure property is met: you may process the task from left to right, as if A is a solution of size N, and A is optimal it has to be also a part of a solution of B, of size N + 1.

So you should build a helper array M, where

for each i < N
 for each j < i
   if a[i] > a[j] && b[i] + M[j] > M[i] then
    M[i] = b[i] + M[j]

And then for the maximum value of M reconstruct the solution.

In some cases there is confusion between sub-array and sub-sequence. Here it should be obvious that sub-sequence is intended.

O(n) Complexity

public static void max_subsequence(Item[] array){
 	String paths[] = new String[array.length];
 	int sum[] = new int[array.length];
 	int max  = Integer.MIN_VALUE;

 	for(int i = 0; i < array.length; i++){
 		sum[i] = array[i].b; 
 		paths[i] = "<" + array[i].a + "," + array[i].b +"> ,";
 		if(sum[i] > max){
 			max = sum[i];
 		}
 	}
 	for(int i = 1; i < array.length; i++){
 		if( array[i-1].a <= array[i].a && (sum[i-1]+ sum[i])> sum[i]){
			paths[i] = paths[i-1] + paths[i];
			sum[i] = sum[i-1] + sum[i];
			if(max < sum[i]){
				max = sum[i];
			}
		}
	}
	for(int i = 0; i < paths.length; i++){
		if(max == sum[i]){
			System.out.println("["+i+"]"+ " MAX: " + paths[i] + " = " + sum[i]);
		}else{
			System.out.println("["+i+"]"+paths[i] + " = " + sum[i]);
		}
	}
 }

axel.david.velazquez following in Ajeet's footsteps

First sort the array based on the first element and save them in an other array call c.
Then we can reduce the problem to find the LCS ( longest Common Subsequence ) problem. Let bi, be the weight whether we choose ai or not, instead of length weight is important here. Using dynamic programming the running time is O(N^2)

Why would you think that the Kadane's Algorithm is the solution? Read the original question again slowly: "the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible" The 2nd element of the pairs is the "maximum possible"... Given the input pairs:

max_subsequence(new Item[]{ 
			new Item(1,-2),
			new Item(2,1),
			new Item(3,-3),
			new Item(4,4),
			new Item(5,-1),
			new Item(6,2),
			new Item(7,1),
			new Item(8,-5),
			new Item(9,4)
		});

integer 6 is not the max possible as the algorithm is determining, 12 is the max possible integer of the 2nd element. First it's assumed that the pairs are sorted based on their first element. Second, remove all pairs where the 2nd element is negative. You end up with this list of pairs:

Item(2,1),
Item(4,4),
Item(6,2),
Item(7,1),
Item(9,4)

The first elements are in increasing order, and the sum of the second elements are the maximum positive integer. If there happen to be additional criteria that there cannot be gaps in the first elements order then that should be noted in the question, but the question just says "increasing order". Are they not increasing order?

Additionally, If the "increasing order" should rule out the fact that the first element of any two pairs is the same number {2,3}, {2,5}, then you would always take the pair with the larger second element.

double getMax(vector< pair<double, double> > v) {
	assert(v.size() > 0);
	int bleft=0, bright=0;
	int tmp_left = 0;
	double bv=v[0].second;
	double cv = bv;
	for (int i = 1; i < v.size(); i++) {
		if (cv < 0 || v[i].first < v[i-1].first) {
			cv = v[i].second;
			tmp_left = i;
		} else {
			cv += v[i].second;	
		}
		if (bv < cv) {
			bleft = tmp_left;
			bright = i;
			bv = cv;
		}
	}
	return bv;
}

Simple in Java

public class GetRequiredRangeInPairArray {

	private static class IntPair {

		int first_;
		int second_;
		IntPair (int f, int s){
			first_ = f; second_ = s;
		}
		int first() { return first_; }
		int second() { return second_; }
		
		@Override
		public String toString() {
			return "["+first()+"," +second()+"]";
		}
	}


	static class Range extends IntPair {
		Range(int s, int e){ super(s,e); }
		int start() { return (int) super.first(); }
		int end () { return (int) super.second(); }

	}
	
	
	// the range includes start but not the end
	public static Range getRequiredSubArray(IntPair [] arr){
		int n = arr.length;
		if(n < 1) return new Range(0,1);
		if(n == 1) return new Range(0,1);

		int maxSum = Integer.MIN_VALUE;
		int maxStart = 0;
		int maxEnd = 0;

		int start = 0;
		int sum = 0;
		int prevFirst = Integer.MIN_VALUE;	
		for(int i = 0;  i < n ; i++){
			IntPair r = arr[i];
			if(sum <=0 || prevFirst >= r.first()){
				start  = i;	
				sum = 0;
			}  

			sum += r.second();

			if(sum > maxSum){
				
				maxSum  = sum;
				maxStart = start;
				maxEnd  = i;
			}
			prevFirst = r.first();

		}


		return new Range(maxStart, maxEnd+1);


	}


	public static void main(String[] args) {
		IntPair [] arr1 = {
				new IntPair(2,Integer.MIN_VALUE),
				new IntPair(1,10),
				new IntPair(3,-5),
				new IntPair(5,-7),
				new IntPair(1,10),
				new IntPair(3,-5),
				new IntPair(5,7),
				new IntPair(5,7),
		};
		System.out.println(getRequiredSubArray(arr1));
	}
	
}

Modified Kadane's algorithm

public class KadaneForPair {

	private class Pair {
		public int a;
		public int b;

		public Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}

	public Pair[] findMaxSubArray(Pair[] input) {
		int start = 0;
		int maxSum = input[0].b;
		int bestSum = input[0].b;

		int bestStart = 0;
		int bestEnd = 0;

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

			/*
			 * we reposition start index only when the continuity of first a
			 * breaks.
			 */
			if (input[i].a < input[i - 1].a) {
				start = i;
				maxSum = input[i].b;
			} else {
				maxSum += input[i].b;
			}

			if (maxSum > bestSum) {
				bestSum = maxSum;
				bestStart = start;
				bestEnd = i;
			}
		}
		System.out.println("bestStart: " + bestStart + " bestEnd: " + bestEnd);
		Pair[] out = new Pair[bestEnd - bestStart + 1];
		System.arraycopy(input, bestStart, out, 0, bestEnd - bestStart + 1);
		return out;
	}

	public static void main(String args[]) {
		KadaneForPair test = new KadaneForPair();
		Pair[] input = new Pair[5];
		input[0] = test.new Pair(10, 2);
		input[1] = test.new Pair(2, 10);
		input[2] = test.new Pair(3, 2);
		input[3] = test.new Pair(5, 87);
		input[4] = test.new Pair(-1, 10);
		Pair[] out = test.findMaxSubArray(input);
		System.out.println("input:");
		display(input);
		System.out.println("output: ");
		display(out);
	}

	private static void display(Pair[] out) {
		for(int i =0;i<out.length;i++){
			System.out.print("(" + out[i].a+ ", " + out[i].b + ") ");
		}
		System.out.println();
	}
}