CareerCup

First of all, we can calculate the cumulative sum of changes and then the answer for maxGain would be the two elements with maximum difference in which the bigger element is on the right of the smaller one.

So we could easily iterate over the array from left to right, update the minimum value we've seen so far, and each time update the best answer we could have.

Here's my code for 1.a an d 1.b
O(N)

pair<int,int> maxGain(vector<int> changes)
{
	vector<int> stock;
	int N=changes.size();
	stock.push_back(changes[0]);
	for (int i=1;i<N;i++)
		stock.push_back(stock[stock.size()-1]+changes[i]);
        //tmp is the index of minimum stock we've seen so far
	int tmp=0,startDay=0,endDay=N-1;
	
	for (int i=1;i<N;i++){
		if (stock[i]-stock[tmp] > stock[endDay]-stock[startDay]){ //for maxLost change it to <
			startDay = tmp;
			endDay = i;
		}
		if (stock[i]<stock[tmp])//for maxLost, change it to >
			tmp = i;
	}


	return make_pair(startDay,endDay);
}

for 1.c, we need to know the minimum value among the last K elements we've seen so far. I used the multiset to storing the values, and if the size of the multiset reaches to K+1, we should remove the first invalid element.In this way we always have the last K valid elements in the multiset.
Also, each time the first element of multiset is the minimum one that we are looking for.
O(N*logK)

pair<int,int> maxGainWithLimit(vector<int> changes,int K)
{
	vector<int> stock;
	int N=changes.size();
	stock.push_back(changes[0]);
	for (int i=1;i<N;i++)
		stock.push_back(stock[stock.size()-1]+changes[i]);
        //multiset for keeping possible repeated values
	multiset< pair<int,int> > st;
	int tmp=0, startDay=0,endDay=N-1;

	st.insert(make_pair(stock[0],0));

	for (int i=1;i<N;i++){

		//first element of set is the minimum of stocks which are not far from K elements

		if ( stock[i] - (*st.begin()).first > stock[endDay] - stock[startDay] ) {
			startDay = (*st.begin()).second;
			endDay = i;
		}

		st.insert(make_pair(stock[i],i));
		if (st.size()==K+1){
			st.erase(make_pair(stock[i-K],i-K));
		}
	}

	return make_pair(startDay,endDay);

}

int main(int argc, char** argv) {

    const int len = 9;
    int data[len] = {-1, -6, 10, 2, -5, 20, 5, -10, 6}; 
    
    int best_value = 0;
    int sum = 0;
    int best_start = 0;
    int best_end = 0;
    int start = 0;
    
    for(int i = 0; i < len; i++)
    {
        sum = sum + data[i];
        if(sum < 0)
        {
            start = i;
            sum = 0;
        }
        else if(sum > best_value)
        {
            best_value = sum;
            best_start = start;
            best_end = i;
        }
    }
    cout << best_start << " " << best_end << " " << best_value;
    
    return 0;
}

here is an O(N) solution based on finding max and min elements in k window:

int maxProfit(vector<int> &nums, int k = 100) {
  int n = nums.size();
  if (n < 2) return 0;
  vector<int> prices{ nums[0] };
  for (int j = 1; j < n; ++j) prices.push_back(prices.back() + nums[j]);
  int maxpro = 0, maxbuy = 0, maxsell = 0, buy = 0, sell = 0, pro = 0;
  deque<int> buytime;
  deque<int> selltime;
  for (int i = 0; i < n; ++i) {
    while (!buytime.empty() && i - buytime.front() >= k) buytime.pop_front();
    while (!buytime.empty() && nums[buytime.front()] >= nums[i]) buytime.pop_front();
    while (!buytime.empty() && nums[i] <= nums[buytime.back()]) buytime.pop_back();
    buytime.push_back(i);
    while (!selltime.empty() && !buytime.empty() && selltime.front() <= buytime.front()) selltime.pop_front();
    while (!selltime.empty() && nums[selltime.front()] <= nums[i]) selltime.pop_front();
    while (!selltime.empty() && nums[i] >= nums[selltime.back()]) selltime.pop_back();
    selltime.push_back(i);
    pro = nums[selltime.front()] - nums[buytime.front()];
    if (maxpro < pro) maxpro = pro;
  }
  return maxpro;
}

The solution is :
Try to find the non-decreasing runs of array. When such a run is found (lets say [start,end], then set currBestBuy = a[start], currBestSell = a[end].
Also if this is not the first run, then check whether (currBestSell - bestBuy) > (currBestSell- currBestBuy) and if so that update the bestSell = currBestSell.
When the entire array is iterated over entirely the bestbuy and bestSell will store the best buy price and best sell price respectively.

Q.1b: solution: to find out the maximum loss just reverse the logic so that you take worstBuy and worstSell price, by finding non-increasing runs of array and then comparing with them with the any last found non-increasing runs of array.

Q.1c: In this case just consider the non-decreasing runs of array of length k only.