// Program by Akash Tripathi (@proakash256)
// Given an Array of the Prices
// of a Stock on Multiple Days.
// Find the Maximum Profit by Buying
// and Selling only one Stock.
#include <stdio.h>
int bruteForce(int *ar , int n)
{
int max_profit = 0;
for(int i = 0; i < n; i = i + 1)
{
int c = 0;
for(int j = i; j < n; j = j + 1)
{
c = ar[j] - ar[i];
if(c > max_profit)
{
max_profit = c;
}
}
}
// Time Complexity = O(n^2)
// Space Complexity = O(1)
return max_profit;
}
int auxillaryArray(int *ar , int n)
{
int max_profit = 0;
// Making right Auxillary Array
int right[n];
right[n - 1] = ar[n - 1];
for(int i = (n - 2); i >= 0; i = i - 1)
{
if(right[i + 1] > ar[i])
right[i] = right[i + 1];
else
right[i] = ar[i];
}
int c = 0;
for(int i = 0; i < n; i = i + 1)
{
c = right[i] - ar[i];
if(c > max_profit)
max_profit = c;
}
// Time Complexity = O(n)
// Space Complexity = O(n)
return max_profit;
}
int thirdMethod(int *ar , int n)
{
int max_profit = 0;
int min_so_far = ar[0];
int profit = 0;
for(int i = 0; i < n; i = i + 1)
{
if(ar[i] < min_so_far)
min_so_far = ar[i];
profit = ar[i] - min_so_far;
if(profit > max_profit)
max_profit = profit;
}
// Time Complexity = O(n)
// Space Complexity = O(1)
return max_profit;
}
int main()
{
int n;
printf("Enter the number of elements : ");
scanf("%d", &n);
int ar[n];
printf("\nEnter the elements :\n");
for (int i = 0; i < n; i = i + 1)
scanf("%d", &ar[i]);
int max_profit = 0;
// This can be solved by three methods:
// First Method:
max_profit = bruteForce(ar , n);
printf("\nMaximum Profit by Brute Force Method
is %d\n" , max_profit);
// Second Method:
max_profit = auxillaryArray(ar , n);
printf("\nMaximum Profit by Auxillary Array
Method is %d\n" , max_profit);
// Third Method:
max_profit = thirdMethod(ar , n);
printf("\nMaximum Profit by Third Method is
%d\n" , max_profit);
return 0;
}
Comments
Post a Comment