### Getting maximum of an array without the use of any external variables

Is there a way I can find the maximum of an array without the use of nested loops / 2nd variable ? maybe or maybe not using swaps too depending on how possible/impossible it is with the first 2 requirements

Cheers!

Also this is a question I tried so hard to think of because I heard it was asked in an interview before but I failed to reach a solution!

No function is to be used, and by 2nd variable I meant the "max" variable we usually use, only allowed to use a loop to iterate through the array elements, we can only use the array elements itself though even if we change all their values for the sake of getting the maximum out of it.
Maybe try using a specific index (the first comes to mind) and compare/swap if needed with the later elements.

Something like:
 ``12345`` ``````for(unsigned int i = 1; i < size; i++) { // Start at 1 since ary[0] will be used as the 'max' variable if(ary[i] > ary[0]) { std::swap(ary[i], ary[0]); } }``````

Of course, this requires that the array is mutable.
Edit:
 No function is to be used

Oops

Use a reduction, i.e., compute
`max(a[0], max(a[1], max(a[2], max(a[3], a[4]))))`
In C++ we write reductions using `std::reduce`, or if C++17 isn't available, `std::accumulate`. The difference between reduce and accumulate is that reduce can nest the function calls in any order, but accumulate always uses the structure above, called a right fold.

This process is called a reduction because the operation reduces a sequence of elements to exactly one element.
 ``12345678910111213`` ``````# include # include // precondition: n >= 1 int fold_max(int* a, int n) { return (n == 1)? a[0]: std::max(a[0], fold_max(a + 1, n - 1)); } int main() { int a[5] = {3, 7, 1, 9, 2}; std::cout << std::accumulate(a, a + 5, 0, std::max) << '\n' << fold_max(a, 5) << '\n'; }``````

http://rextester.com/SIK73208
Last edited on
With no functions or recursion allowed, you can use a similar process:

 ``123456789`` ``````int main() { static constexpr int n = 5; int a[n] = {3, 7, 1, 9, 2}; for (int i = n - 1; i >= 1; --i) { a[i - 1] = a[i] > a[i - 1]? a[i]: a[i - 1]; } std::cout << a[0] << '\n'; }``````

http://rextester.com/UONW72801
Last edited on
closed account (48T7M4Gy)
https://stackoverflow.com/questions/34315002/max-in-a-c-array

 ``123456789`` ``````#include int main() { int array[]{ 3, 123, -14, 1, 5, 9 }; size_t size = sizeof(array)/sizeof(int); std::cout << "Maximum: " << *std::max_element(array , array + size) << '\n'; }``````

Or completely without extra variables:
 ``1234567`` ``````#include int main() { int array[]{ 3, 123, -14, 1, 5, 9 }; std::cout << "Maximum: " << *std::max_element(array, array + sizeof(array)/sizeof(int)) << '\n'; }``````
Last edited on
@kemort but its without using stl library tho, it wasnt a c++ question it was a general question to test the approach
Since you can swap elements of the array, just use one pass of bubble sort to bubble the max element to the end of the array:
 ``123456789101112131415`` ``````#include #include int main() { int array[]{ 3, 123, -14, 1, 5, 9 }; size_t size = sizeof(array)/sizeof(int); for (size_t i=0; i < size-1; ++i) { if (array[i] > array[i+1]) { std::swap(array[i], array[i+1]); } } std::cout << array[size-1] << '\n'; }``````

> I meant the "max" variable we usually use, only allowed to use a loop to iterate through the
> array elements, we can only use the array elements itself though
> even if we change all their values for the sake of getting the maximum out of it.

We certainly can't use std::swap for int (it would use an extra variable).
We can use an xor swap algorithm if the array contains integer values.

However since this is allowed: "change all their values for the sake of getting the maximum out of it", by using array[0] as 'the "max" variable we usually use', we can relax the restriction that that the array must contain integer values.

 ``1234`` ``````std::string array[] = { "efg", "abcd", "wxy", "mnop", "ghijkl" } ; // since for( const auto& v : array ) if( array[0] < v ) array[0] = v ; std::cout << "max: " << array[0] << '\n' ;``````
Topic archived. No new replies allowed.