个性化阅读
专注于IT技术分析

两个元素之间的最大差,使得较大的元素出现在较小的数字之后

本文概述

给定整数数组arr[], 找出任意两个元素之间的最大差值, 以使较大的元素出现在较小的数字之后。

例子 :

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.

方法1(简单)

使用两个循环。在外循环中, 拾取元素一个接一个, 在内循环中, 计算拾取的元素与数组中每个其他元素的差, 并将该差与迄今为止计算出的最大差进行比较。下面是上述方法的实现:

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

#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

// 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) 
     {
         MaximumDiffrence maxdif = new MaximumDiffrence();
         int arr[] = { 1 , 2 , 90 , 10 , 110 };
         System.out.println( "Maximum differnce is " + 
                                 maxdif.maxDiff(arr, 5 ));
     }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

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

// 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 differnce is " + 
                                 maxDiff(arr, 5));
     }
}
  
// This code is contributed by Sam007

PHP

<?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)

输出:

Maximum difference is 109

时间复杂度:

O(n ^ 2)

辅助空间:

O(1)

方法2(棘手而又高效)

在这种方法中, 我们不采用选取的元素与其他元素的差异, 而是采用迄今为止找到的最小元素的差异。因此, 我们需要跟踪两件事:

1)到目前为止发现的最大差异(max_diff)。

2)到目前为止访问的最小人数(min_element)。

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)
{
      // 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;
}

C

#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

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

Python3

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

// 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
// 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
?>

输出如下:

Maximum difference is 109

时间复杂度:O(n)

辅助空间:O(1)

像min元素一样, 我们也可以从右侧跟踪max元素。

感谢Katamaran建议这种方法。

下面是实现:

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

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

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

// 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
// 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
?>

输出如下:

Maximum difference is 109

方法3(另一个棘手的解决方案)

首先找到数组的相邻元素之间的差异, 并将所有差异存储在大小为n-1的辅助数组diff []中。现在, 这个问题变成寻找该差值数组的最大和子数组。

感谢Shubham Mittal提出此解决方案。

下面是实现:

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

C

#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

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

Python3

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

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

输出如下:

Maximum difference is 98

时间复杂度:

上)

辅助空间:

上)

我们可以修改上述方法以在O(1)额外空间中工作。无需创建辅助数组, 我们可以在同一循环中计算差异和最大和。以下是空间优化版本。

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

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

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

// 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
// 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
?>

输出如下:

Maximum difference is 98

时间复杂度:O(n)

辅助空间:O(1)

以下是此问题的变体:

矩阵中两行元素之和的最大差

如果你发现上述代码/算法中的任何错误, 或找到其他解决相同问题的方法, 请发表评论

赞(0) 打赏
未经允许不得转载:srcmini » 两个元素之间的最大差,使得较大的元素出现在较小的数字之后
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏