Pair LargestSubArray(int [] A, int sum) { HashMap <int, int> H = new HasMap<int, int>(); // Cumulative sum is the key. // The value is the leftmost index. H.Insert(0, 0); int Sum = 0; int max_left = 0; int max_right = 0; int max_len = 0; for(int j = 0; j < A.Length; j++) { Sum += A[j]; if (H.containsKey(Sum-N)) { int possible_left = H[Sum-N]; int possible_right = j; int possible_len = possible_right - possible_left; if (possible_len>= max_len) { max_left = possible_left; max_right = possible_right; max_len = possible_len; } } if (!H.ContainsKey(Sum)) { H[Sum] = j+1; } } return new Pair(max_left, max_right); }
Read full article from Given a array, find the larges... | CareerCup
No comments:
Post a Comment