I've been trying to get into coding and need some help with my code. I figured out how to get the maximum difference, but I also want to print the numbers used to get that difference. For example, a-b=diff, I want to print a, b, and diff separately. My friend also challenged me to get the smaller value first, then get the bigger value. Now, once I pick a certain element in the array as the smallest number, I'm only allowed to pick through the next elements for the biggest number. For example, if the array is {2, 3, 4, 15, 8, 1}, it should be 15 - 2, not 15 - 1.
Here is my code to get the maximum difference/what I have so far:
#include <iostream>
using namespace std;
int maximum_difference(int arr[], int n)
{
int max_num = arr[1];
int min_num = arr[0];
int max_difference = max_num - min_num;
for (int i = 0; i < n; i )
{
for (int j = i 1; j < n; j )
{
if (arr[j] - arr[i] > max_difference)
{
max_num=arr[j];
min_num=arr[i];
max_difference = max_num - min_num;
}
}
}
return max_difference;
}
int main()
{
int n;
cout<<"elements: ";
cin >> n;
int arr[n];
for(int i=0; i<n; i )
{
cin >> arr[i];
}
cout << "Maximum difference is " << maximum_difference(arr, n);
return 0;
}
What should I add or replace, so that I could cout max_num and min_num together with the max_difference?
CodePudding user response：
You don't need to use two for loops for finding the max and min values of the array. Additionally, in Standard C the size of an array must be a compile-time constant. So when you wrote:
int n;
cin >> n;
int arr[n]; //NOT STANDARD C
The statement int arr[n]; is not standard C since n is not a constant expression.
Better would be to use std::vector as shown below:
Method 1: Manually finding max and min values
#include <iostream>
#include <vector>
#include <climits>
//this function take a vector as input and returns the difference b/w max and min values
int maximum_difference(const std::vector<int>& arr)
{
int max_num = INT_MIN;
int min_num = INT_MAX;
//iterate through the vector to find the max and min value
for(const int& element: arr)
{
if(element > max_num)
{
max_num = element;
}
if(element < min_num)
{
min_num = element;
}
}
return max_num - min_num; //return the difference of mx and min value
}
int main()
{
int n;
std::cout<<"elements: ";
std::cin >> n;
//create vector of int of size n
std::vector<int> arr(n);
//take elements from user
for(int i=0; i<n; i )
{
std::cin >> arr[i];
}
std::cout << "Maximum difference is " << maximum_difference(arr);
return 0;
}
Method 2: Using std::minmax_element to find the max and min values
Here we use std::minmax_element which returns a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second.
#include <iostream>
#include<vector>
#include<algorithm>
int main()
{
int n;
std::cout<<"elements: ";
std::cin >> n;
//create vector of int of size n
std::vector<int> arr(n);
//take elements from user
for(int i=0; i<n; i )
{
std::cin >> arr[i];
}
auto it = std::minmax_element(arr.begin(), arr.end());
std::cout << "The max difference is " << *it.second - *it.first;
return 0;
}
CodePudding user response：
Does it help?
#include <stdio.h>
#include <stdlib.h>
int maximum_difference(int arr[], int n)
{
//Init to same number
int max_num = arr[0];
int min_num = arr[0];
int difference;
//Find max and min by single traverse
for (int j = 1; j < n; j )
{
if (max_num < arr[j])
{
max_num = arr[j];
}
if(min_num > arr[j])
{
min_num = arr[j];
}
}
/*
|----.--.--.--.--.--.--.--|
|..-3 -2 0 1 2 3 .. |
*/
if( max_num >= 0 && min_num >= 0) //both are ve numbers
difference = max_num - min_num;
else if(max_num > 0 && min_num < 0) //max is positve and min is negative
difference = max_num abs(min_num);
else //both are -negative
difference = abs(abs(max_num) - abs(min_num)); //abs value is the difference between max and min
return difference;
}
int main()
{
int n;
int arr[100];
printf("How many elements: ");
scanf("%d", &n);
//validate
if(n == 0 || n < 0)
printf("Enter valid number in 1..100");
if(n >100)
printf("The program can parse 100 elements at Maximum. Enter 1..100");
//read inputs
printf("\nEnter the integers: ");
for(int i=0; i<n; i )
{
scanf("%d", &arr[i]);
}
//display difference
printf("\nMaximum difference is %d", maximum_difference(arr, n));
return 0;
}
CodePudding user response：
I will address the algorithm part of this. The C part doesn't interest me; once you see the solution you'll know why.
We must choose indices i and j such that i <= j and a[j] - a[i] is maximized.
Your example sequence:
a = [2, 3, 4, 15, 8, 1]
Find the incremental maximum values starting from the right. (Most readers will immediately get the rest of the solution given this one hint).
maxs = [15, 15, 15, 15, 8, 1]
Find the incremental minimum values starting from the left.
mins = [2, 2, 2, 2, 2, 1]
Subtract them to find the greatest possible differences.
diffs = [13, 13, 13, 13, 6, 0]
The maximum element in this array, 13 is the largest value of a[j] - a[i] possible.
To find the actual values of i and j we store the indices of our best value for i and indices for the corresponding best value for j.
bestj = [3, 3, 3, 3, 4, 5]
besti = [0, 0, 0, 0, 0, 5]
We can compute the best difference the same way as before, but indirectly via the indices. For each k, diffs[k] = a[bestj[k]] - a[besti[k]] which still produces the same diffs as before:
diffs = [13, 13, 13, 13, 6, 0]
And when we find the index of the maximum diff, any such index will do. There may be multiple solutions, but this will find one solution (values for i and j) that produces a maximal result. Suppose we identify index k as having the maximal value 13, theni = besti[k] and j = bestj[k].
And therefore one solution is i = 0 and j = 3.
confirm:
a = [2, 3, 4, 15, 8, 1]
^i ^^j
i = 0
j = 3
a[i] = 2
a[j] = 15
a[j] - a[i] = 13
So again, I'm not going to provide the code, but if you can write a loop to scan from right to left computing incremental maximums as you go (as shown above), then you can code it up easily.