search

Finding the maximum difference between adjacent items of a list of 5 numbers in Java

2 years ago
Komentar: 142013
Dibaca: 99

Maximum adjacent difference in an array in its sorted form

Given an array, find the maximum difference between its two consecutive elements in its sorted form.
Examples:

Show
Input: arr[] = {1, 10, 5} Output: 5 Sorted array would be {1, 5, 10} and maximum adjacent difference would be 10 - 5 = 5 Input: arr[] = {2, 4, 8, 11} Output: 4

Maximum difference between two elements such that larger element appears after the smaller number

Given an array arr[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number.

Examples :

Input : arr = {2, 3, 10, 6, 4, 8, 1} Output : 8 Explanation : The maximum difference is between 10 and 2. Input : arr = {7, 9, 5, 6, 3, 2} Output : 2 Explanation : The maximum difference is between 9 and 7.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

Method 1 (Simple)
Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far. Below is the implementation of the above approach :




// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
for (int i = 0; i < arr_size; i++)
{
for (int j = i+1; j < arr_size; j++)
{
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 90, 10, 110};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);
return 0;
}




#include<stdio.h>
/* The function assumes that there are at least two
elements in array.
The function returns a negative value if the array is
sorted in decreasing order.
Returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int i, j;
for (i = 0; i < arr_size; i++)
{
for (j = i+1; j < arr_size; j++)
{
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 90, 10, 110};
printf("Maximum difference is %d", maxDiff(arr, 5));
getchar();
return 0;
}




// Java program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
class MaximumDiffrence
{
/* The function assumes that there are at least two
elements in array.
The function returns a negative value if the array is
sorted in decreasing order.
Returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int i, j;
for (i = 0; i < arr_size; i++)
{
for (j = i + 1; j < arr_size; j++)
{
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
MaximumDifference maxdif = new MaximumDifference();
int arr[] = {1, 2, 90, 10, 110};
System.out.println("Maximum difference is " +
maxdif.maxDiff(arr, 5));
}
}
// This code has been contributed by Mayank Jaiswal




# Python 3 code to find Maximum difference
# between two elements such that larger
# element appears after the smaller number
# The function assumes that there are at
# least two elements in array. The function
# returns a negative value if the array is
# sorted in decreasing order. Returns 0
# if elements are equal
def maxDiff(arr, arr_size):
max_diff = arr[1] - arr[0]
for i in range( 0, arr_size ):
for j in range( i+1, arr_size ):
if(arr[j] - arr[i] > max_diff):
max_diff = arr[j] - arr[i]
return max_diff
# Driver program to test above function
arr = [1, 2, 90, 10, 110]
size = len(arr)
print ("Maximum difference is", maxDiff(arr, size))
# This code is contributed by Swetank Modi




// C# code to find Maximum difference
using System;
class GFG {
// The function assumes that there
// are at least two elements in array.
// The function returns a negative
// value if the array is sorted in
// decreasing order. Returns 0 if
// elements are equal
static int maxDiff(int[] arr, int arr_size)
{
int max_diff = arr[1] - arr[0];
int i, j;
for (i = 0; i < arr_size; i++) {
for (j = i + 1; j < arr_size; j++) {
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 90, 10, 110 };
Console.Write("Maximum difference is " +
maxDiff(arr, 5));
}
}
// This code is contributed by Sam007




<?php
// PHP program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff($arr, $arr_size)
{
$max_diff = $arr[1] - $arr[0];
for ($i = 0; $i < $arr_size; $i++)
{
for ($j = $i+1; $j < $arr_size; $j++)
{
if ($arr[$j] - $arr[$i] > $max_diff)
$max_diff = $arr[$j] - $arr[$i];
}
}
return $max_diff;
}
// Driver Code
$arr = array(1, 2, 90, 10, 110);
$n = sizeof($arr);
// Function calling
echo "Maximum difference is " .
maxDiff($arr, $n);
// This code is contributed
// by Akanksha Rai(Abby_akku)




<script>
// javascript program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff( arr, arr_size)
{
let max_diff = arr[1] - arr[0];
for (let i = 0; i < arr_size; i++)
{
for (let j = i+1; j < arr_size; j++)
{
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
// Driver program to test above function
let arr = [1, 2, 90, 10, 110];
let n = arr.length;
// Function calling
document.write("Maximum difference is " + maxDiff(arr, n));
// This code is contributed by jana_sayantan.
</script>

Output :

Maximum difference is 109

Time Complexity : O(n^2)
Auxiliary Space : O(1)



Method 2 (Tricky and Efficient)
In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element).




// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
// Maximum difference found so far
int max_diff = arr[1] - arr[0];
// Minimum number visited so far
int min_element = arr[0];
for(int i = 1; i < arr_size; i++)
{
if (arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 90, 10, 110};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);
return 0;
}




#include<stdio.h>
/* The function assumes that there are at least two
elements in array.
The function returns a negative value if the array is
sorted in decreasing order.
Returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for(i = 1; i < arr_size; i++)
{
if (arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 6, 80, 100};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum difference is %d", maxDiff(arr, size));
getchar();
return 0;
}




// Java program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
class MaximumDiffrence
{
/* The function assumes that there are at least two
elements in array.
The function returns a negative value if the array is
sorted in decreasing order.
Returns 0 if elements are equal */
int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for (i = 1; i < arr_size; i++)
{
if (arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}
/* Driver program to test above functions */
public static void main(String[] args)
{
MaximumDiffrence maxdif = new MaximumDiffrence();
int arr[] = {1, 2, 90, 10, 110};
int size = arr.length;
System.out.println("MaximumDifference is " +
maxdif.maxDiff(arr, size));
}
}
// This code has been contributed by Mayank Jaiswal




# Python 3 code to find Maximum difference
# between two elements such that larger
# element appears after the smaller number
# The function assumes that there are
# at least two elements in array.
# The function returns a negative
# value if the array is sorted in
# decreasing order. Returns 0 if
# elements are equal
def maxDiff(arr, arr_size):
max_diff = arr[1] - arr[0]
min_element = arr[0]
for i in range( 1, arr_size ):
if (arr[i] - min_element > max_diff):
max_diff = arr[i] - min_element
if (arr[i] < min_element):
min_element = arr[i]
return max_diff
# Driver program to test above function
arr = [1, 2, 6, 80, 100]
size = len(arr)
print ("Maximum difference is",
maxDiff(arr, size))
# This code is contributed by Swetank Modi




// C# code to find Maximum difference
using System;
class GFG {
// The function assumes that there
// are at least two elements in array.
// The function returns a negative
// value if the array is sorted in
// decreasing order.Returns 0 if
// elements are equal
static int maxDiff(int[] arr, int arr_size)
{
int max_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for (i = 1; i < arr_size; i++) {
if (arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 90, 10, 110 };
int size = arr.Length;
Console.Write("MaximumDifference is " +
maxDiff(arr, size));
}
}
// This code is contributed by Sam007




<?php
// PHP program to find Maximum
// difference between two elements
// such that larger element appears
// after the smaller number
// The function assumes that there
// are at least two elements in array.
// The function returns a negative
// value if the array is sorted in
// decreasing order and returns 0
// if elements are equal
function maxDiff($arr, $arr_size)
{
// Maximum difference found so far
$max_diff = $arr[1] - $arr[0];
// Minimum number visited so far
$min_element = $arr[0];
for($i = 1; $i < $arr_size; $i++)
{
if ($arr[$i] - $min_element > $max_diff)
$max_diff = $arr[$i] - $min_element;
if ($arr[$i] < $min_element)
$min_element = $arr[$i];
}
return $max_diff;
}
// Driver Code
$arr = array(1, 2, 90, 10, 110);
$n = count($arr);
// Function calling
echo "Maximum difference is " .
maxDiff($arr, $n);
// This code is contributed by Sam007
?>




<script>
// Javascript code to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
// The function assumes that there
// are at least two elements in array.
// The function returns a negative
// value if the array is sorted in
// decreasing order.Returns 0 if
// elements are equal
function maxDiff(arr, arr_size)
{
let max_diff = arr[1] - arr[0];
let min_element = arr[0];
let i;
for (i = 1; i < arr_size; i++) {
if (arr[i] - min_element > max_diff)
max_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return max_diff;
}
let arr = [ 1, 2, 90, 10, 110 ];
let size = arr.length;
document.write("Maximum difference is " + maxDiff(arr, size));
</script>

Output:

Maximum difference is 109

Time Complexity : O(n)
Auxiliary Space : O(1)

Like min element, we can also keep track of max element from right side. Thanks to Katamaran for suggesting this approach. Below is the implementation :




// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
// Initialize Result
int maxDiff = -1;
// Initialize max element from right side
int maxRight = arr[n-1];
for (int i = n-2; i >= 0; i--)
{
if (arr[i] > maxRight)
maxRight = arr[i];
else
{
int diff = maxRight - arr[i];
if (diff > maxDiff)
{
maxDiff = diff;
}
}
}
return maxDiff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 90, 10, 110};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);
return 0;
}




// Java program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
import java.io.*;
class GFG {
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
static int maxDiff(int arr[], int n)
{
// Initialize Result
int maxDiff = -1;
// Initialize max element from right side
int maxRight = arr[n-1];
for (int i = n-2; i >= 0; i--)
{
if (arr[i] > maxRight)
maxRight = arr[i];
else
{
int diff = maxRight - arr[i];
if (diff > maxDiff)
{
maxDiff = diff;
}
}
}
return maxDiff;
}
/* Driver program to test above function */
public static void main (String[] args) {
int arr[] = {1, 2, 90, 10, 110};
int n = arr.length;
// Function calling
System.out.println ("Maximum difference is " + maxDiff(arr, n));
}
//This code is contributed by Tushil..
}




# Python3 program to find Maximum difference
# between two elements such that larger
# element appears after the smaller number
# The function assumes that there are
# at least two elements in array. The
# function returns a negative value if the
# array is sorted in decreasing order and
# returns 0 if elements are equal
def maxDiff(arr, n):
# Initialize Result
maxDiff = -1
# Initialize max element from
# right side
maxRight = arr[n - 1]
for i in range(n - 2, -1, -1):
if (arr[i] > maxRight):
maxRight = arr[i]
else:
diff = maxRight - arr[i]
if (diff > maxDiff):
maxDiff = diff
return maxDiff
# Driver Code
if __name__ == '__main__':
arr = [1, 2, 90, 10, 110]
n = len(arr)
# Function calling
print("Maximum difference is",
maxDiff(arr, n))
# This code is contributed by 29AjayKumar




// C# program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
using System;
class GFG
{
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
static int maxDiff(int[] arr, int n)
{
// Initialize Result
int maxDiff = -1;
// Initialize max element from right side
int maxRight = arr[n-1];
for (int i = n-2; i >= 0; i--)
{
if (arr[i] > maxRight)
maxRight = arr[i];
else
{
int diff = maxRight - arr[i];
if (diff > maxDiff)
{
maxDiff = diff;
}
}
}
return maxDiff;
}
// Driver Code
public static void Main ()
{
int[] arr = {1, 2, 90, 10, 110};
int n = arr.Length;
// Function calling
Console.WriteLine("Maximum difference is " +
maxDiff(arr, n));
}
}
// This code is contributed
// by Akanksha Rai




<?php
// PHP program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff($arr, $n)
{
// Initialize Result
$maxDiff = -1;
// Initialize max element from
// right side
$maxRight = $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
{
if ($arr[$i] > $maxRight)
$maxRight = $arr[$i];
else
{
$diff = $maxRight - $arr[$i];
if ($diff > $maxDiff)
{
$maxDiff = $diff;
}
}
}
return $maxDiff;
}
// Driver Code
$arr = array(1, 2, 90, 10, 110);
$n = sizeof($arr);
// Function calling
echo "Maximum difference is ",
maxDiff($arr, $n);
// This code is contributed by ajit
?>




<script>
// Javascript program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff(arr, n)
{
// Initialize Result
let maxDiff = -1;
// Initialize max element from right side
let maxRight = arr[n-1];
for (let i = n-2; i >= 0; i--)
{
if (arr[i] > maxRight)
maxRight = arr[i];
else
{
let diff = maxRight - arr[i];
if (diff > maxDiff)
{
maxDiff = diff;
}
}
}
return maxDiff;
}
let arr = [1, 2, 90, 10, 110];
let n = arr.length;
// Function calling
document.write("Maximum difference is " + maxDiff(arr, n));
</script>

Output:

Maximum difference is 109

Method 3 (Another Tricky Solution)
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.Thanks to Shubham Mittal for suggesting this solution. Below is the implementation :




// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1.
// The array will hold the difference
// of adjacent elements
int diff[n-1];
for (int i=0; i < n-1; i++)
diff[i] = arr[i+1] - arr[i];
// Now find the maximum sum
// subarray in diff array
int max_diff = diff[0];
for (int i=1; i<n-1; i++)
{
if (diff[i-1] > 0)
diff[i] += diff[i-1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);
return 0;
}




#include<stdio.h>
int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1. The array will hold
// the difference of adjacent elements
int diff[n-1];
for (int i=0; i < n-1; i++)
diff[i] = arr[i+1] - arr[i];
// Now find the maximum sum subarray in diff array
int max_diff = diff[0];
for (int i=1; i<n-1; i++)
{
if (diff[i-1] > 0)
diff[i] += diff[i-1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum difference is %d", maxDiff(arr, size));
return 0;
}




// Java program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
class MaximumDiffrence
{
int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1. The array will hold
// the difference of adjacent elements
int diff[] = new int[n - 1];
for (int i = 0; i < n - 1; i++)
diff[i] = arr[i + 1] - arr[i];
// Now find the maximum sum subarray in diff array
int max_diff = diff[0];
for (int i = 1; i < n - 1; i++)
{
if (diff[i - 1] > 0)
diff[i] += diff[i - 1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
// Driver program to test above functions
public static void main(String[] args)
{
MaximumDiffrence mxdif = new MaximumDiffrence();
int arr[] = {80, 2, 6, 3, 100};
int size = arr.length;
System.out.println(mxdif.maxDiff(arr, size));
}
}
// This code has been contributed by Mayank Jaiswal




# Python 3 code to find Maximum difference
# between two elements such that larger
# element appears after the smaller number
def maxDiff(arr, n):
diff = [0] * (n - 1)
for i in range (0, n-1):
diff[i] = arr[i+1] - arr[i]
# Now find the maximum sum
# subarray in diff array
max_diff = diff[0]
for i in range(1, n-1):
if (diff[i-1] > 0):
diff[i] += diff[i-1]
if (max_diff < diff[i]):
max_diff = diff[i]
return max_diff
# Driver program to test above function
arr = [80, 2, 6, 3, 100]
size = len(arr)
print ("Maximum difference is",
maxDiff(arr, size))
# This code is contributed by Swetank Modi




// C# code to find Maximum difference
using System;
class GFG {
static int maxDiff(int[] arr, int n)
{
// Create a diff array of size n-1.
// The array will hold the
// difference of adjacent elements
int[] diff = new int[n - 1];
for (int i = 0; i < n - 1; i++)
diff[i] = arr[i + 1] - arr[i];
// Now find the maximum sum
// subarray in diff array
int max_diff = diff[0];
for (int i = 1; i < n - 1; i++) {
if (diff[i - 1] > 0)
diff[i] += diff[i - 1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
// Driver code
public static void Main()
{
int[] arr = { 80, 2, 6, 3, 100 };
int size = arr.Length;
Console.Write(maxDiff(arr, size));
}
}
// This code is contributed by Sam007




<?php
// PHP program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff($arr, $n)
{
// Create a diff array of size n-1.
// The array will hold the difference
// of adjacent elements
$diff[$n-1] = array();
for ($i=0; $i < $n-1; $i++)
$diff[$i] = $arr[$i+1] - $arr[$i];
// Now find the maximum sum
// subarray in diff array
$max_diff = $diff[0];
for ($i=1; $i<$n-1; $i++)
{
if ($diff[$i-1] > 0)
$diff[$i] += $diff[$i-1];
if ($max_diff < $diff[$i])
$max_diff = $diff[$i];
}
return $max_diff;
}
// Driver Code
$arr = array(80, 2, 6, 3, 100);
$n = sizeof($arr);
// Function calling
echo "Maximum difference is " .
maxDiff($arr, $n);
// This code is contributed
// by Akanksha Rai




<script>
// JavaScript program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff(arr, n)
{
// Create a diff array of size n-1.
// The array will hold the difference
// of adjacent elements
let diff = new Array(n - 1);
for(let i = 0; i < n - 1; i++)
diff[i] = arr[i + 1] - arr[i];
// Now find the maximum sum
// subarray in diff array
let max_diff = diff[0];
for(let i = 1; i < n - 1; i++)
{
if (diff[i - 1] > 0)
diff[i] += diff[i - 1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
// Driver code
let arr = [ 80, 2, 6, 3, 100 ];
let n = arr.length;
// Function calling
document.write("Maximum difference is " +
maxDiff(arr, n));
// This code is contributed by Mayank Tyagi
</script>

Output:

Maximum difference is 98

Time Complexity : O(n)
Auxiliary Space : O(n)

We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.




// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff (int arr[], int n)
{
// Initialize diff, current sum and max sum
int diff = arr[1]-arr[0];
int curr_sum = diff;
int max_sum = curr_sum;
for(int i=1; i<n-1; i++)
{
// Calculate current diff
diff = arr[i+1]-arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr[0]);
// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);
return 0;
}




// Java program to find Maximum
// difference between two elements
// such that larger element appears
// after the smaller number
class GFG
{
/* The function assumes that there
are at least two elements in array.
The function returns a negative
value if the array is sorted in
decreasing order and returns 0 if
elements are equal */
static int maxDiff (int arr[], int n)
{
// Initialize diff, current
// sum and max sum
int diff = arr[1] - arr[0];
int curr_sum = diff;
int max_sum = curr_sum;
for(int i = 1; i < n - 1; i++)
{
// Calculate current diff
diff = arr[i + 1] - arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {80, 2, 6, 3, 100};
int n = arr.length;
// Function calling
System.out.print("Maximum difference is " +
maxDiff(arr, n));
}
}
// This code is contributed by Smitha




# Python3 program to find Maximum difference
# between two elements such that larger
# element appears after the smaller number
# The function assumes that there are
# at least two elements in array. The
# function returns a negative value if
# the array is sorted in decreasing
# order and returns 0 if elements are equal
def maxDiff (arr, n):
# Initialize diff, current
# sum and max sum
diff = arr[1] - arr[0]
curr_sum = diff
max_sum = curr_sum
for i in range(1, n - 1):
# Calculate current diff
diff = arr[i + 1] - arr[i]
# Calculate current sum
if (curr_sum > 0):
curr_sum += diff
else:
curr_sum = diff
# Update max sum, if needed
if (curr_sum > max_sum):
max_sum = curr_sum
return max_sum
# Driver Code
if __name__ == '__main__':
arr = [80, 2, 6, 3, 100]
n = len(arr)
# Function calling
print("Maximum difference is",
maxDiff(arr, n))
# This code is contributed
# by 29AjayKumar




// C# program to find Maximum
// difference between two elements
// such that larger element appears
// after the smaller number
using System;
class GFG
{
/* The function assumes that there
are at least two elements in array.
The function returns a negative
value if the array is sorted in
decreasing order and returns 0 if
elements are equal */
static int maxDiff (int[] arr, int n)
{
// Initialize diff, current
// sum and max sum
int diff = arr[1] - arr[0];
int curr_sum = diff;
int max_sum = curr_sum;
for(int i = 1; i < n - 1; i++)
{
// Calculate current diff
diff = arr[i + 1] - arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
// Driver Code
public static void Main()
{
int[] arr = {80, 2, 6, 3, 100};
int n = arr.Length;
// Function calling
Console.WriteLine("Maximum difference is " +
maxDiff(arr, n));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)




<?php
// PHP program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
function maxDiff ($arr, $n)
{
// Initialize diff, current sum
// and max sum
$diff = $arr[1] - $arr[0];
$curr_sum = $diff;
$max_sum = $curr_sum;
for($i = 1; $i < $n - 1; $i++)
{
// Calculate current diff
$diff = $arr[$i + 1] - $arr[$i];
// Calculate current sum
if ($curr_sum > 0)
$curr_sum += $diff;
else
$curr_sum = $diff;
// Update max sum, if needed
if ($curr_sum > $max_sum)
$max_sum = $curr_sum;
}
return $max_sum;
}
// Driver Code
$arr = array(80, 2, 6, 3, 100);
$n = sizeof($arr);
// Function calling
echo "Maximum difference is ",
maxDiff($arr, $n);
// This code is contributed
// by Sach_code
?>




<script>
// Javascript program to find Maximum
// difference between two elements
// such that larger element appears
// after the smaller number
/* The function assumes that there
are at least two elements in array.
The function returns a negative
value if the array is sorted in
decreasing order and returns 0 if
elements are equal */
function maxDiff (arr, n)
{
// Initialize diff, current
// sum and max sum
let diff = arr[1] - arr[0];
let curr_sum = diff;
let max_sum = curr_sum;
for(let i = 1; i < n - 1; i++)
{
// Calculate current diff
diff = arr[i + 1] - arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
// Driver Code
let arr = [ 80, 2, 6, 3, 100 ];
let n = arr.length;
// Function calling
document.write("Maximum difference is " +
maxDiff(arr, n));
// This code is contributed by rag2127
</script>

Output:

Maximum difference is 98

Time Complexity : O(n)
Auxiliary Space : O(1)

Below is a variation of this problem:
Maximum difference of sum of elements in two rows in a matrix
Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem

Finding the maximum difference between adjacent items of a list of 5 numbers in Java




Article Tags :
Arrays
Amazon
Hike
MakeMyTrip
Ola Cabs
SAP Labs
Practice Tags :
Amazon
Hike
MakeMyTrip
Ola Cabs
SAP Labs
Arrays
Read Full Article

C


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <limits.h>
// Utility function to find a maximum of two numbers
int max(int x, int y) {
return (x > y) ? x : y;
}
// Naive function to find the maximum difference between two elements in
// an array such that the smaller element appears before the larger element
int getMaxDiff(int arr[], int n)
{
int diff = INT_MIN;
if (n == 0) {
return diff;
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
diff = max(diff, arr[j] - arr[i]);
}
}
}
return diff;
}
int main()
{
int arr[] = { 2, 7, 9, 5, 1, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int result = getMaxDiff(arr, n);
if (result != INT_MIN) {
printf("The maximum difference is %d", result);
}
return 0;
}

DownloadRun Code

Output:

The maximum difference is 7

Maximum adjacent difference in an array in its sorted form in C++

C++Server Side ProgrammingProgramming

We are given with an array. The array need not be sorted. The task is to find the maximum difference between adjacent elements of that array in its sorted form. So the first thing is to sort the array in increasing or decreasing order. Then we will iterate the array and calculate the adjacent difference of Arr[i+1]-Arr[i]. Then for each iteration we will compare this difference with the one which is found maximum so far.

Input − Arr[] = [ 1,5,10,2,7 ]

Output − Maximum adjacent difference in array in its sorted form is 3.

Explanation − Sorted Arr[] in increasing order = [ 1,2,5,7,10 ]. So the adjacent differences are as follows −

Arr[1]-Arr[0]=1, Maximum Difference=1 Arr[2]-Arr[1]=3, Maximum Difference=3 Arr[3]-Arr[2]=2, Maximum Difference=3 Arr[4]-Arr[3]=3, Maximum Difference=3

Input − Arr[] = [ 5,11,21,15,20 ]

Output − Maximum adjacent difference in array in its sorted form is 6.

Explanation − Sorted Arr[] in increasing order = [ 5,11,15,20,21 ]. So the adjacent differences are as follows −

Arr[1]-Arr[0]=6, Maximum Difference=6 Arr[2]-Arr[1]=4, Maximum Difference=6 Arr[3]-Arr[2]=5, Maximum Difference=6 Arr[4]-Arr[3]=1, Maximum Difference=6


Method 1 (Simple)
Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far. Below is the implementation of the above approach :



C++

// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;
/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[],int arr_size)
{
int max_diff = arr[1] - arr[0];
for (int i = 0; i < arr_size; i++)
{
for (int j = i+1; j < arr_size; j++)
{
if (arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 90, 10, 110};
int n =sizeof(arr) /sizeof(arr[0]);
// Function calling
cout <<"Maximum difference is " << maxDiff(arr, n);
return 0;
}

C program to find maximum difference between two elements

#include <stdio.h> /* This function returns the maximum difference between two elements of array, such that larger elements is after smaller element*/ int getMaxDiff(int *array, int size) { /* Initialize maxDiff with diference of first two element */ int i, j; int maxDiff = array[1] - array[0]; /* For every element, check it's difference with all other larger elements */ for(i = 0; i < size; i++){ for(j = i+1; j < size; j++){ if((array[j] - array[i] > maxDiff) && (array[j] > array[i])) maxDiff = array[j] - array[i]; } } return maxDiff; } int main(){ int array[10] = {7, 3, 9, 1, 0, -4, 7, 2, 5, 6}; int maxDiff = getMaxDiff(array, 10); printf("Maximum Difference : %d", maxDiff); return 0; } Output
Maximum Difference : 11
Optimized approach : O(n)
  • Traverse inputArray from index 0 to N-1 and keep tract of the minimum element found till now(min) and maximum difference between any two element till now(maxDiff).
  • Let current element is inputArray[i], difference between the current element and minimum element found till now is greater than maxDiff(array[i] - min > maxDiff) then update maxDiff.
  • If array[i] is less than min, then update min.

Top List List

Pos Terkait

You are given a list of n numbers each of which is either prime or composite
You are given a list of n numbers each of which is either prime or composite

Python program to find the second largest number in a list using bubble sort
Python program to find the second largest number in a list using bubble sort

Write a program to find minimum and maximum elements from a list of integers
Write a program to find minimum and maximum elements from a list of integers

Mengapa pada listrik statis arus listriknya atau muatan listrik yang tidak mengalir
Mengapa pada listrik statis arus listriknya atau muatan listrik yang tidak mengalir

Which is not possible for linked list?
Which is not possible for linked list?

Write a Python program to sort each sublist of strings in a given list of lists
Write a Python program to sort each sublist of strings in a given list of lists

Write a program which will accept two lists comprising of different numbers in C
Write a program which will accept two lists comprising of different numbers in C

Given a list of integers write a Python code to triple all the values in the list
Given a list of integers write a Python code to triple all the values in the list

Write a Python program to find the union and intersection of two user given lists
Write a Python program to find the union and intersection of two user given lists

Write a python program to enter two lists and merge them. also display merged list
Write a python program to enter two lists and merge them. also display merged list

Periklanan

BERITA TERKINI

Bisakah Anda mengaktifkan javascript di ponsel?
1 years ago . by AdorableMantra
Bagaimana Anda menghapus teks duplikat dengan python?
1 years ago . by DecreasingEmperor
Cara menghapus latar belakang video di CapCut
1 years ago . by SkepticalDugout
Apa itu rounddown dalam excel?
1 years ago . by JollyDollar
Dapatkan array multidimensi kunci php
1 years ago . by LuridRecognition
Cara mengeluarkan darah haid yang tidak keluar
1 years ago . by CuriousRedundancy
Dapatkan javascript bulan dengan 0
1 years ago . by NastyMedics
Python cetak daftar daftar secara vertikal
1 years ago . by DeviantColors
Cara membersihkan kacamata yang tergores
1 years ago . by Two-storyDealing
Cara menggunakan variable to dataframe python
1 years ago . by ThrobbingMetaphysics

Toplist Popular

#1
Top 10 berikut ini yang bukan merupakan penetapan tujuan visi perusahaan adalah 2022
1 years ago
#2
Top 10 sebuah bak air berbentuk balok dengan ukuran panjang 40 cm, lebar 30 cm, dan tinggi 35 cm 2022
1 years ago
#3
Top 9 banjir bukan sekadar bencana alam paragraf 3 gagasan utama 2022
1 years ago
#4
Top 10 diketahui himpunan himpunan sebagai berikut p bilangan ganjil yang kurang dari 15 2022
1 years ago
#5
Top 10 penyelesaian dari persamaan 3x 2 y 9 dan 2x y 3 adalah 2022
1 years ago
#6
Top 10 bagaimana cara memberi salam kepada orang tua dan guru yang benar brainly 2022
1 years ago
#7
Top 10 semakin tinggi nilai toleransi semakin tinggi nilai integrasi nasional 2022
1 years ago
#8
Top 10 benda kerajinan tidak boleh membahayakan pemakainya maka benda kerajinan memiliki prinsip 2022
1 years ago
#9
Top 9 bagian tutup sumbat termos biasanya terbuat dari benda berjenis brainly 2022
1 years ago
#10
Top 9 pernyataan yang sesuai dengan prinsipteori evolusi jb lamarck ditunjukkan oleh angka 2022
1 years ago

Periklanan

Terpopuler

Token Data

Periklanan

Tentang Kami

Legal

Dukungan

Social

homeenfritzhtrjako
Copyright © 2024 idkuu.com Inc.