The maximum is not of all
Remember that there is usually a simpler and faster solution than the one that comes to mind first.
Donald Knuth
Task
Find the maximum negative element in the array.
Knowing the standard algorithm for finding the maximum element in an array, it is possible, by analogy, to write a program that solves this problem, adding only a check for the sign of the array element.
Program fragment
M = A[0];
for (i=1; i<N; i++)
if ((A[i]<0) && (A[i]>M))
M = A[i];
cout << M;
This solution will not always work correctly. Before reading any further, try to find a test yourself that will cause this program to work incorrectly.
Answer: A test in which the first element of the array is equal to any non-negative number will cause the solution to be incorrect.
The wrong decision is obtained due to the fact that we "without looking" written to the variable
M the value of the first element of the array. Since we do not need all the elements of the array, but only negative ones, therefore, we must first write the first negative element into the
M variable. You can fix the program by adding, for example, such a fragment
// we will go through all the elements of the array,
// until we meet a negative element
int i = 0;
while (i < n && A[i] >= 0)
i++; // move to the next element of the array
// if i is less than n,
// so we found a negative element
if (i<n)
{
// look for the maximum negative of the remaining elements
M = A[0];
int start = i + 1;
for (i = start; i < N; i++)
if ((A[i] < 0) && (A[i] > M))
M = A[i];
cout << M;
}
else
cout << "There are no such elements";
The program turned out to be quite cumbersome. In the worst case, we will have to go through the entire array almost twice from the beginning to the last element.
In fact, the program can be reduced to one cycle.
M = A[0];
for (i=1; i<N; i++)
{
//if we met a negative element of the array,
// check next condition
if (A[i]<0)
// bold condition will allow
// write the first encountered negative element to the variable M,
// if A[0] was non-negative
if ((M >= 0) && (A[i]>M))
M = A[i];
}
cout << M;
To successfully complete task No. 25 of the USE, you do not need to write an effective program. Therefore, if you cannot find a short solution to the problem, write it down as you can. But remember that programming is all about practice.