Author: Rahul Sharma
Tester: Naman Mittal
Editorialist: Rahul Sharma
DIFFICULTY:
EASY
PREREQUISITES:
Arrays
PROBLEM:
Given a positive integer array of size N. Find the sum of running stream of difference between pair of maximum and minimum. Note index of maximum \geq index of minimum.
EXPLANATION:
Take two variables currentMin and currentMax and initialize them with first element of array. First we will try to achieve minimum so far.
Iterate the array if element at index i is less than currentMin and currentMin is not yet achieved update currentMIn else set minFlag.
Similarly if element is greater that currentMax and update currentMax else set maxFlag.
Once minFlag and maxFlag are set updates sum = sum + (currentMax-currentMin) and set currentMin and currentMax to current element and reset the flags.
COMPLEXITIES:
Time Complexity: O(N) for each test case
Space Complexitiy: O(1) for each test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
long long int arr[10000000] = {0};
long long int maxProfit(long long int arr[], long long int n)
{
long long int minCost = arr[0];
long long int maxCost = arr[0];
long long int profit = 0;
bool buy = true;
bool sell = true;
for(int i = 1; i < n; i++)
{
if (arr[i] <= arr[i-1] && buy)
minCost = maxCost = arr[i];
else if (arr[i] > arr[i-1])
{
buy = false;
maxCost = arr[i];
}
else
{
buy = sell = true;
profit = profit + maxCost - minCost;
maxCost = minCost = arr[i];
}
}
return profit + maxCost - minCost;
}
int main()
{
long long int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << maxProfit(arr,n) << '\n';
}