tushar2702
BAN USERWhat if the array is {2,3,5} and my sum = 6. The array has number 3 in it - at that point, it will do hashmap.containsKey(sum – array[ i ]) = 3 and it will say it is present in the hashmap and the pair will be 3,3 that sums up to 6. But we don't want that as we have just one 3 in the array and not two of them.
- tushar2702 September 17, 2014Yes, so then my solution works for the e.g. you gave. Initialy index_i and index_j are set to 0. Within the for loop it won't satisfy any constraint and once exits index_i and index_j will remain 0. What's wrong in my solution?? correct me if i am wrong!
- tushar2702 October 21, 2013Oh thanks for the feedback. So in this e.g. it should retrun 0,2 right?
- tushar2702 October 21, 2013Here is an implementation of Kadane's algorithm. It also handles the case where all numbers are negative.
public class MaximumSubarray {
static int arr[] = {8,9,-6,0,3,9} ;
public static void main(String args[]) {
int curr_max = arr[0];
int max_so_far = arr[0];
int index_i = 0;
int index_j = 0;
for (int i=1; i<arr.length; i++) {
if (arr[i] > curr_max + arr[i]) {
index_i = i;
}
curr_max = Math.max(arr[i], curr_max + arr[i]);
if (curr_max > max_so_far) {
index_j = i;
}
max_so_far = Math.max(curr_max, max_so_far);
}
System.out.println(max_so_far);
System.out.println(index_i);
System.out.println(index_j);
}
}
We can use dynamic programming here.
findMaxSum(int index) {
return Math.max(arr[index] + findMaxSum(index+1) , findMaxSum(index+1));
}
This is not the entire code just the idea. This will just give you the max sum. The logic can be tweaked to get the index.
- tushar2702 October 12, 2013
Solving this in 2 steps:
Consider a hashset: hs, uniqueSum which is sum of all unique numbers initialized to 0 and a totalSum which is a sum of all numbers in the array.
Step 1:
Step 2:
So e.g. array = {1,2,3,4,5,6,5,5,5,5}
- tushar2702 January 13, 2016uniqueSum = 20; totalSum = 40
duplicateNumber = 5