amfaheem
BAN USER/**
* @author Ahmed Fahim
* Created on October 5, 2012, 058:20 AM
*/
public static void DutchNationalFlag(int[] A) {
int posStartIndex = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] <= 0) {
int temp = A[i];
for (int j = i; j > posStartIndex; j--) {
A[j] = A[j-1];
}
A[posStartIndex] = temp;
if (A[i] < 0) posStartIndex++;
}
}
}
This is a DP problem called maximum subarray (check wikipedia for that problem), here's modified version for Kadane's algorithm which stores array indexes of the maximum subarray:
/**
* @author Ahmed Fahim
* Created on October 4, 2012, 058:20 AM
*/
public static int[] maxSubarray(int A[]) {
int max_so_far = 0;
int max_ending_here = 0;
int start = 0;
int end = 0;
for (int i = 0; i < A.length; i++) {
if (max_ending_here + A[i] > 0) {
max_ending_here = max_ending_here + A[i];
start = min(start, i);
} else {
max_ending_here = 0;
start = i+1;
}
if (max_ending_here > max_so_far) {
end = i;
max_so_far = max_ending_here;
}
}
return Arrays.copyOfRange(A, start, end + 1);
}
public static int max(int x, int y) {
return x >= y
? x
: y;
}
public static int min(int x, int y) {
return x <= y
? x
: y;
}
but this way, we would sort -ve and +ve numbers, where you are asked to preserve their original order
- amfaheem October 05, 2012