最大化arr[j]-arr[i]+arr[l]-arr[k]，使i-yiteyi-C++库

最大化arr[j]-arr[i]+arr[l]-arr[k]，使i

null

例子：

Let us say our array is {4, 8, 9, 2, 20}Then the maximum such value is 23 (9 - 4 + 20 - 2)

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

蛮力法： 我们可以简单地找到给定约束条件下大小4的所有组合。最大值将是所需的答案。这种方法效率很低。

有效方法（动态规划）： 我们将使用动态规划来解决这个问题。为此，我们创建了四个一维DP表。假设有四个DP表，分别为表1[]，表2[]，表3[]，表4[] 然后求出arr[l]-arr[k]+arr[j]-arr[i]的最大值，使i 表1[]应存储arr[l]的最大值表2[]应存储arr[l]–arr[k]的最大值表3[]应存储arr[l]–arr[k]+arr[j]的最大值表4[]应存储arr[l]–arr[k]+arr[j]–arr[i]的最大值那么最大值将出现在表4的索引0中，这将是我们需要的答案。

以下是上述想法的实施情况——

C++

                             /* A C++ Program to find maximum value of                           
                             arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,                           
                             given that the array has atleast 4 elements */                           
                             #include <bits/stdc++.h>                           
                             using                                           namespace                                           std;                           
             
                             // To represent minus infinite                           
                             #define MIN -100000000                           
             
                             // A Dynamic Programming based function to find maximum                           
                             // value of arr[l] - arr[k] + arr[j] - arr[i] is maximum                           
                             // and i < j < k < l                           
                             int                                           findMaxValue(                                           int                                           arr[],                                           int                                           n)                           
                             {                           
                                                         // If the array has less than 4 elements                           
                                                         if                                           (n < 4)                           
                                                         {                           
                                                         printf                                           (                                           "The array should have atlest 4 elements"                                           );                           
                                                         return                                           MIN;                           
                                                         }                           
             
                                                         // We create 4 DP tables                           
                                                         int                                           table1[n + 1], table2[n], table3[n - 1], table4[n - 2];                           
             
                                                         // Initialize all the tables to MIN                           
                                                         for                                           (                                           int                                           i=0; i<=n; i++)                           
                                                         table1[i] = table2[i] = table3[i] = table4[i] =  MIN;                           
             
                                                         // table1[] stores the maximum value of arr[l]                           
                                                         for                                           (                                           int                                           i = n - 1; i >= 0; i--)                           
                                                         table1[i] = max(table1[i + 1], arr[i]);                           
             
                                                         // table2[] stores the maximum value of arr[l] - arr[k]                           
                                                         for                                           (                                           int                                           i = n - 2; i >= 0; i--)                           
                                                         table2[i] = max(table2[i + 1], table1[i + 1] - arr[i]);                           
             
                                                         // table3[] stores the maximum value of arr[l] - arr[k]                           
                                                         // + arr[j]                           
                                                         for                                           (                                           int                                           i = n - 3; i >= 0; i--)                           
                                                         table3[i] = max(table3[i + 1], table2[i + 1] + arr[i]);                           
             
                                                         // table4[] stores the maximum value of arr[l] - arr[k]                           
                                                         // + arr[j] - arr[i]                           
                                                         for                                           (                                           int                                           i = n - 4; i >= 0; i--)                           
                                                         table4[i] = max(table4[i + 1], table3[i + 1] - arr[i]);                           
             
                                                         /*for (int i = 0; i < n + 1; i++)                           
                                                         cout << table1[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n; i++)                           
                                                         cout << table2[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n - 1; i++)                           
                                                         cout << table3[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n - 2; i++)                           
                                                         cout << table4[i] << " " ;                           
                                                         cout << endl;                           
                                                         */                           
             
                                                         // maximum value would be present in table4[0]                           
                                                         return                                           table4[0];                           
                             }                           
             
                             // Driver Program to test above functions                           
                             int                                           main()                           
                             {                           
                                                         int                                           arr[] = { 4, 8, 9, 2, 20 };                           
                                                         int                                           n =                                           sizeof                                           (arr) /                                           sizeof                                           (arr[0]);                           
             
                                                         printf                                           (                                           "%d"                                           , findMaxValue(arr, n));                           
             
                                                         return                                           0;                           
                             }                           

JAVA

                             /* A Java Program to find maximum value of                           
                             arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,                           
                             given that the array has atleast 4 elements */                           
                             import                                           java.util.Arrays;                           
             
                             class                                           GFG                           
                             {                           
                                                         // A Dynamic Programming based function                           
                                                         // to find maximum value of                           
                                                         // arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         // is maximum and i < j < k < l                           
                                                         static                                           int                                           findMaxValue(                                           int                                           [] arr,                                           int                                           n)                           
                                                         {                           
             
                                                         // If the array has less than 4 elements                           
                                                         if                                           (n <                                           4                                           )                           
                                                         {                           
                                                         System.out.println(                                           "The array should have"                                           +                           
                                                         " atleast 4 elements"                                           );                           
                                                         }                           
             
                                                         // We create 4 DP tables                           
                                                         int                                           table1[] =                                           new                                           int                                           [n +                                           1                                           ];                           
                                                         int                                           table2[] =                                           new                                           int                                           [n];                           
                                                         int                                           table3[] =                                           new                                           int                                           [n -                                           1                                           ];                           
                                                         int                                           table4[] =                                           new                                           int                                           [n -                                           2                                           ];                           
             
                                                         // Initialize all the tables to minus Infinity                           
                                                         Arrays.fill(table1, Integer.MIN_VALUE);                           
                                                         Arrays.fill(table2, Integer.MIN_VALUE);                           
                                                         Arrays.fill(table3, Integer.MIN_VALUE);                           
                                                         Arrays.fill(table4, Integer.MIN_VALUE);                           
             
                                                         // table1[] stores the maximum value of arr[l]                           
                                                         for                                           (                                           int                                           i = n -                                           1                                           ; i >=                                           0                                           ; i--)                           
                                                         {                           
                                                         table1[i] = Math.max(table1[i +                                           1                                           ], arr[i]);                           
                                                         }                           
             
                                                         // table2[] stores the maximum value of                           
                                                         // arr[l] - arr[k]                           
                                                         for                                           (                                           int                                           i = n -                                           2                                           ; i >=                                           0                                           ; i--)                           
                                                         {                           
                                                         table2[i] = Math.max(table2[i +                                           1                                           ],                           
                                                         table1[i +                                           1                                           ] - arr[i]);                           
                                                         }                           
             
                                                         // table3[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j]                           
                                                         for                                           (                                           int                                           i = n -                                           3                                           ; i >=                                           0                                           ; i--)                           
                                                         table3[i] = Math.max(table3[i +                                           1                                           ],                           
                                                         table2[i +                                           1                                           ] + arr[i]);                           
             
                                                         // table4[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         for                                           (                                           int                                           i = n -                                           4                                           ; i >=                                           0                                           ; i--)                           
                                                         table4[i] = Math.max(table4[i +                                           1                                           ],                           
                                                         table3[i +                                           1                                           ] - arr[i]);                           
             
                                                         return                                           table4[                                           0                                           ];                           
                                                         }                           
             
                                                         // Driver Code                           
                                                         public                                           static                                           void                                           main(String[] args)                           
                                                         {                           
                                                         int                                           arr[] = {                                           4                                           ,                                           8                                           ,                                           9                                           ,                                           2                                           ,                                           20                                           };                           
                                                         int                                           n = arr.length;                           
                                                         System.out.println(findMaxValue(arr, n));                           
                                                         }                           
                             }                           
             
                             // This code is contributed by Vivekkumar Singh                           

Python3

                             # A Python3 Program to find maximum value of                           
                             # arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,                           
                             # given that the array has atleast 4 elements                           
             
                             # A Dynamic Programming based function to find                           
                             # maximum value of arr[l] - arr[k] + arr[j] - arr[i]                           
                             # is maximum and i < j < k < l                           
                             def                                           findMaxValue(arr, n):                           
             
                                                         # If the array has less than 4 elements                           
                                                         if                                           n <                                           4                                           :                           
                                         
                                                         print                                           (                                           "The array should have atlest 4 elements"                                           )                           
                                                         return                                           MIN                           
             
                                                         # We create 4 DP tables                           
                                                         table1, table2                                           =                                           [                                           MIN                                           ]                                           *                                           (n                                           +                                           1                                           ), [                                           MIN                                           ]                                           *                                           n                           
                                                         table3, table4                                           =                                           [                                           MIN                                           ]                                           *                                           (n                                           -                                           1                                           ), [                                           MIN                                           ]                                           *                                           (n                                           -                                           2                                           )                           
             
                                                         # table1[] stores the maximum value of arr[l]                           
                                                         for                                           i                                           in                                           range                                           (n                                           -                                           1                                           ,                                           -                                           1                                           ,                                           -                                           1                                           ):                           
                                                         table1[i]                                           =                                           max                                           (table1[i                                           +                                           1                                           ], arr[i])                           
             
                                                         # table2[] stores the maximum                           
                                                         # value of arr[l] - arr[k]                           
                                                         for                                           i                                           in                                           range                                           (n                                           -                                           2                                           ,                                           -                                           1                                           ,                                           -                                           1                                           ):                           
                                                         table2[i]                                           =                                           max                                           (table2[i                                           +                                           1                                           ],                           
                                                         table1[i                                           +                                           1                                           ]                                           -                                           arr[i])                           
             
                                                         # table3[] stores the maximum value of                           
                                                         # arr[l] - arr[k] + arr[j]                           
                                                         for                                           i                                           in                                           range                                           (n                                           -                                           3                                           ,                                           -                                           1                                           ,                                           -                                           1                                           ):                           
                                                         table3[i]                                           =                                           max                                           (table3[i                                           +                                           1                                           ],                           
                                                         table2[i                                           +                                           1                                           ]                                           +                                           arr[i])                           
             
                                                         # table4[] stores the maximum value of                           
                                                         # arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         for                                           i                                           in                                           range                                           (n                                           -                                           4                                           ,                                           -                                           1                                           ,                                           -                                           1                                           ):                           
                                                         table4[i]                                           =                                           max                                           (table4[i                                           +                                           1                                           ],                           
                                                         table3[i                                           +                                           1                                           ]                                           -                                           arr[i])                           
             
                                                         # maximum value would be present in table4[0]                           
                                                         return                                           table4[                                           0                                           ]                           
             
                             # Driver Code                           
                             if                                           __name__                                           =                                           =                                           "__main__"                                           :                           
             
                                                         arr                                           =                                           [                                           4                                           ,                                           8                                           ,                                           9                                           ,                                           2                                           ,                                           20                                           ]                           
                                                         n                                           =                                           len                                           (arr)                           
                                         
                                                         # To represent minus infinite                           
                                                         MIN                                           =                                           -                                           100000000                           
             
                                                         print                                           (findMaxValue(arr, n))                           
             
                             # This code is contributed by Rituraj Jain                           

C#

                             // C# Program to find maximum value of                           
                             // arr[l] - arr[k] + arr[j] - arr[i]                           
                             // and i < j < k < l, given that                           
                             // the array has atleast 4 elements                           
                             using                                           System;                           
             
                             class                                           GFG                           
                             {                           
                                                         // A Dynamic Programming based function                           
                                                         // to find maximum value of                           
                                                         // arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         // is maximum and i < j < k < l                           
                                                         static                                           int                                           findMaxValue(                                           int                                           [] arr,                                           int                                           n)                           
                                                         {                           
             
                                                         // If the array has less than 4 elements                           
                                                         if                                           (n < 4)                           
                                                         {                           
                                                         Console.WriteLine(                                           "The array should have"                                           +                           
                                                         " atleast 4 elements"                                           );                           
                                                         }                           
             
                                                         // We create 4 DP tables                           
                                                         int                                           []table1 =                                           new                                           int                                           [n + 1];                           
                                                         int                                           []table2 =                                           new                                           int                                           [n];                           
                                                         int                                           []table3 =                                           new                                           int                                           [n - 1];                           
                                                         int                                           []table4 =                                           new                                           int                                           [n - 2];                           
             
                                                         // Initialize all the tables to minus Infinity                           
                                                         fill(table1,                                           int                                           .MinValue);                           
                                                         fill(table2,                                           int                                           .MinValue);                           
                                                         fill(table3,                                           int                                           .MinValue);                           
                                                         fill(table4,                                           int                                           .MinValue);                           
             
                                                         // table1[] stores the maximum value of arr[l]                           
                                                         for                                           (                                           int                                           i = n - 1; i >= 0; i--)                           
                                                         {                           
                                                         table1[i] = Math.Max(table1[i + 1], arr[i]);                           
                                                         }                           
             
                                                         // table2[] stores the maximum value of                           
                                                         // arr[l] - arr[k]                           
                                                         for                                           (                                           int                                           i = n - 2; i >= 0; i--)                           
                                                         {                           
                                                         table2[i] = Math.Max(table2[i + 1],                           
                                                         table1[i + 1] - arr[i]);                           
                                                         }                           
             
                                                         // table3[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j]                           
                                                         for                                           (                                           int                                           i = n - 3; i >= 0; i--)                           
                                                         table3[i] = Math.Max(table3[i + 1],                           
                                                         table2[i + 1] + arr[i]);                           
             
                                                         // table4[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         for                                           (                                           int                                           i = n - 4; i >= 0; i--)                           
                                                         table4[i] = Math.Max(table4[i + 1],                           
                                                         table3[i + 1] - arr[i]);                           
             
                                                         return                                           table4[0];                           
                                                         }                           
                                                         static                                           void                                           fill(                                           int                                           [] arr,                                           int                                           val)                           
                                                         {                           
                                                         for                                           (                                           int                                           i = 0; i < arr.Length; i++)                           
                                                         arr[i] = val;                           
                                                         }                           
                                         
                                                         // Driver Code                           
                                                         public                                           static                                           void                                           Main(String[] args)                           
                                                         {                           
                                                         int                                           []arr = { 4, 8, 9, 2, 20 };                           
                                                         int                                           n = arr.Length;                           
                                                         Console.WriteLine(findMaxValue(arr, n));                           
                                                         }                           
                             }                           
             
                             // This code is contributed by Princi Singh                           

Javascript

                             <script>                           
             
                             /* A Javascript program to find maximum value of                           
                             arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,                           
                             given that the array has atleast 4 elements */                           
             
                             // To represent minus infinite                           
                             let MIN = -100000000                           
             
                             // A Dynamic Programming based function to                           
                             // find maximum value of arr[l] - arr[k]                           
                             // + arr[j] - arr[i] is maximum and                           
                             // i < j < k < l                           
                             function                                           findMaxValue(arr, n)                           
                             {                           
                                         
                                                         // If the array has less than 4 elements                           
                                                         if                                           (n < 4)                           
                                                         {                           
                                                         document.write(                                           "The array should have "                                           +                           
                                                         "atlest 4 elements"                                           );                           
                                                         return                                           MIN;                           
                                                         }                           
             
                                                         // We create 4 DP tables                           
                                                         let table1 =                                           new                                           Array(n + 1);                           
                                                         let table2 =                                           new                                           Array(n);                           
                                                         let table3 =                                           new                                           Array(n - 1);                           
                                                         let table4 =                                           new                                           Array(n - 2);                           
             
                                                         // Initialize all the tables to MIN                           
                                                         for                                           (let i = 0; i <= n; i++)                           
                                                         table1[i] = table2[i] =                           
                                                         table3[i] = table4[i] = MIN;                           
             
                                                         // table1[] stores the maximum value of arr[l]                           
                                                         for                                           (let i = n - 1; i >= 0; i--)                           
                                                         table1[i] = Math.max(table1[i + 1], arr[i]);                           
             
                                                         // table2[] stores the maximum value                           
                                                         // of arr[l] - arr[k]                           
                                                         for                                           (let i = n - 2; i >= 0; i--)                           
                                                         table2[i] = Math.max(table2[i + 1],                           
                                                         table1[i + 1] - arr[i]);                           
             
                                                         // table3[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j]                           
                                                         for                                           (let i = n - 3; i >= 0; i--)                           
                                                         table3[i] = Math.max(table3[i + 1],                           
                                                         table2[i + 1] + arr[i]);                           
             
                                                         // table4[] stores the maximum value of                           
                                                         // arr[l] - arr[k] + arr[j] - arr[i]                           
                                                         for                                           (let i = n - 4; i >= 0; i--)                           
                                                         table4[i] = Math.max(table4[i + 1],                           
                                                         table3[i + 1] - arr[i]);                           
             
                                                         /*for (int i = 0; i < n + 1; i++)                           
                                                         cout << table1[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n; i++)                           
                                                         cout << table2[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n - 1; i++)                           
                                                         cout << table3[i] << " " ;                           
                                                         cout << endl;                           
             
                                                         for (int i = 0; i < n - 2; i++)                           
                                                         cout << table4[i] << " " ;                           
                                                         cout << endl;                           
                                                         */                           
             
                                                         // Maximum value would be present in table4[0]                           
                                                         return                                           table4[0];                           
                             }                           
             
                             // Driver code                           
                             let arr = [ 4, 8, 9, 2, 20 ];                           
                             let n = arr.length;                           
             
                             document.write(findMaxValue(arr, n));                           
             
                             // This code is contributed by _saurabh_jaiswal                           
             
                             </script>                           

输出：

时间复杂性： O（n），其中n是输入数组的大小 辅助空间： 因为我们要创建四个表来存储我们的值，所以空间是4*O（n）=O（4*n）=O（n）

读者练习： 这个问题简单而有力。在给定的条件下，这个问题可以推广到任何表达式。求出arr[j]-2*arr[i]+3*arr[l]-7*arr[k]的最大值，使i 本文由 拉希特·贝尔瓦里亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章