CareerCup

1. Build index as following,
					head
					    |
		search_index | search_index| ....| search_index
			|							|
	search_index  ... search_index	search_index ... search_index
		|										|
	number array								number array

2. Call SearchMaxValue function multiple times, the comparison of each time < 500.


struct Search_Index
{
	int start_idx;
	int max_value;
	vector< Search_Index> sub_index;
	vector<int> num_buf;
};

struct Search_Index_Head
{
	int start_idx;
	int end_idx;
	vector< Search_Index> search_idx;
};

Search_Index_Head BuildSearchStruct(const vector<int>& A)
{
	Search_Index_Head head;
	vector< Search_Index> result;
	for (int i = 0; i < A.size(); i += 10000)
	{
		Search_Index new_idx;
		new_idx.start_idx = i;
		int max_val = INT_MIN;
		for (int j = 0; j < 10000; j += 100)
		{
			Search_Index sub_idx;
			sub_idx.start_idx = j;
			int max_sub_val = INT_MIN;
			for (int k = 0; k < 100; k++)
			{
				max_sub_val = max(max_sub_val, A[i + j + k]);
				sub_idx.num_buf.emplace_back(A[i + j + k]);
			}
			sub_idx.max_value = max_sub_val;
			new_idx.sub_index.emplace_back(move(sub_idx));
			max_val = max(max_val, max_sub_val);
		}
		new_idx.max_value = max_val;
		result.emplace_back(move(new_idx));
	}
	head.search_idx = move(result);
	head.start_idx = 0;
	head.end_idx = A.size() - 1;

	return move(head);
}

int SearchMaxValue(Search_Index_Head& head, int start, int end)
{
	if (start < head.start_idx) start = head.start_idx;
	if (end > head.end_idx) end = head.end_idx;
	if (start > end) swap(start, end);

	vector< Search_Index>& idx_buf = head.search_idx;
	int first_start_idx = start / 10000;
	int second_start_idx = (start % 10000) / 100;
	int third_start_idx = (start % 10000) % 100;
	int first_end_idx = end / 10000;
	int second_end_idx = (end % 10000) / 100;
	int third_end_idx = (end % 10000) % 100;

	Search_Index& s_idx_1 = idx_buf[first_start_idx];
	Search_Index& s_idx_2 = s_idx_1.sub_index[second_start_idx];
	int max_val = INT_MIN;
	for (int i = third_start_idx; i < 100; i++)
		max_val = max(max_val, s_idx_2.num_buf[i]);

	for (int i = second_start_idx+1; i < 100; i++)
		max_val = max(max_val, s_idx_1.sub_index[i].max_value);

	Search_Index& e_idx_1 = idx_buf[first_end_idx];
	Search_Index& e_idx_2 = e_idx_1.sub_index[second_end_idx];
	for (int i = first_start_idx+1; i < first_end_idx; i++)
		max_val = max(max_val, idx_buf[i].max_value);

	for (int i = 0; i < second_end_idx; i++)
		max_val = max(max_val, e_idx_1.sub_index[i].max_value);

	for (int i = 0; i <= third_end_idx; i++)
		max_val = max(max_val, e_idx_2.num_buf[i]);

	return max_val;
}

int main()
{
	vector<int> A(1000000, 0);
	int val = 1;
	for (int i = 0; i < 2500; i++)
	{
		for (int j = 0; j < 200; j++)
		{
			val += j + i;
			A[i*400+j] = val;
		}

		for (int j = 0; j < 200; j++)
		{
			val -= i;
			A[i * 400 + 200 + j] = val;
		}
	}
	Search_Index_Head head = BuildSearchStruct(A);
	int start = 12520, end = 83267;
	int max = SearchMaxValue(head, start, end);

	start = 0; end = 4000;
	max = SearchMaxValue(head, start, end);

	return 0;
}