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

[Kalcor]

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.

[edge6768]

Maybe try using a specific index (the first comes to mind) and compare/swap if needed with the later elements.

Something like:

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.

[mbozzi]

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.

# include <iostream>
# include <numeric>

// 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<int>) << '\n'
              << fold_max(a, 5) << '\n';
}

http://rextester.com/SIK73208

[mbozzi]

With no functions or recursion allowed, you can use a similar process:

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

[48T7M4Gy]

Adapted from, http://en.cppreference.com/w/cpp/algorithm/max_element and
https://stackoverflow.com/questions/34315002/max-in-a-c-array

#include <iostream>

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:

#include <iostream>

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

[Kalcor]

@kemort but its without using stl library tho, it wasnt a c++ question it was a general question to test the approach

[dhayden]

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:

#include <iostream>
#include <algorithm>

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';
}

[JLBorges]

> 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.

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' ;