最大子矩阵和问题_最大和问题

电玩女神 2023-03-05 09:36 13阅读 0赞

最大子矩阵和问题

**Description:**

**描述：**

In this article, we would see how to convert a recursion into dynamic programming to solve the maximum sum problem? This can be featured in any interview coding round.

在本文中，我们将看到如何将递归转换为动态编程以解决最大和问题？ 这可以在任何采访编码回合中体现。

**Problem statement:**

**问题陈述：**

Given a number **n**, we can divide it into only three parts **n/2**, **n/3** and **n/4** (we will consider only integer part). The task is to find the maximum sum we can make by dividing the number into three parts recursively and summing up them together.

给定一个数字**n** ，我们可以将其分为三部分**n / 2** ， **n / 3**和**n / 4** (我们将仅考虑整数部分)。 我们的任务是找到最大的总和，方法是将数字递归分为三部分，然后将它们加在一起。

**Note:** Sometimes, the maximum sum can be obtained by not dividing **n**.

**注意：**有时，最大总和可以通过不除**n**来获得。

Input:
        The first line of input contains an integer T denoting the number of test cases. 
        Then T test cases follow. The first line of each test case contains the integer n.
        
        Output:
        For each test case, in a new line, print the maximum sum possible.

**Example:**

**例：**

Input:
        2
        12 
        24
    
        Output:
        13 
        27

**Explanation:**

**说明：**

Say for the first example,
        N=12
    
        N can be divided in n/2(6), n/3(4) & n/4(3). 
        6 can be divided as 3, 2, 1. 
        3 can be divided as 1, 1, 0
        So if n=3 then max sum possible is 3 itself
    
        2 can be divided as 1, 0, 0
        So if n=2 then max sum possible is 2 itself
        1 can't be divided so, if n=1 then max sum possible is 1 itself
    
        So, for n=6 max sum possible is either 6 or 3+2+1 whichever maximum, and its 6
    
        Similarly for n=4 max sum possible is 4 (do it yourself)
        For n=3, max sum possible is 3 (already found while computing for 6)
    
        So for n=12
        Max sum possible is either 12 or (max sum (6) + max sum (4) + max sum (3) = 13), 
        so it's 13
        Check the following tree for proper understanding.
        
    
        
    
        Try the second example of n=24 yourself.

![Maximum sum problem][]

**Solution approach:**

**解决方法：**

Obviously, this is recursion. The recursive algorithm can be,

显然，这是递归。 递归算法可以是

Function axsum:
            1) Base case: if n is 0 or n is 1 return n;
            2) Return maximum( n,maxsum(n/2) + maxsum(n/3)+maxsum(n/4))

This is the same as what I did in the above explanation. Compute until you reach the base case. But, the recursive solution will generate many overlapping subproblems which will be computed again and again. Check the above recursion tree for **n=12**, and you can find there have been multiple instances of subproblem **3 & 2** which are to be computed multiple times. If such small input generates these many overlapping subproblems then for large input it will be computationally very expensive. So, to overcome this overhead, we use dynamic programming which is storing the computed subproblems and use it whenever required again without further computing. This will reduce the overhead.

这与我在上述说明中所做的相同。 计算直到达到基本情况。 但是，递归解决方案将生成许多重叠的子问题，这些子问题将一次又一次地计算出来。 检查上面的递归树是否为**n = 12** ，您可以发现存在子问题**3和2的**多个实例，这些实例需要多次计算。 如果这么小的输入产生了这么多重叠的子问题，那么对于大的输入，它将在计算上非常昂贵。 因此，为了克服这种开销，我们使用动态编程来存储计算出的子问题，并在需要时再次使用它而无需进一步计算。 这将减少开销。

To store the computations we use **dp** an array with dimension equal to input size **n**

为了存储计算，我们使用**dp**一个维度等于输入大小**n**的数组

So,

所以，

1)  Initialize dp[n+1] with the index value. 
            That is, dp[0]=0,dp[1]=1 ,dp[2] =2 and so on. 
            This covers to thing.
                i)  It covers base case that is for n=0 or 1
                ii) It initializes each sub problem of size i with value i 
                    which is the least value of the maximum sum. 
                    If maximum sum can't be availed by dividing then 
                    it will return i,sub problem size 
        2)  for i=2 to n
                dp[i]=maximum(dp[i],dp[i/2]+dp[i/3]+dp[i/4])   
        3)  Return dp[n]

**This has time complexity of O(n) and space complexity of O(n).**

**这具有O(n)的时间复杂度和O(n)的空间复杂度。**

**N.B:** To bring more optimization on multiple test cases, create a global array and pre-compute it. The global array should be based on input constraints. Check the following implementation.

**注意：**要对多个测试用例进行更多优化，请创建一个全局数组并对其进行预先计算。 全局数组应基于输入约束。 检查以下实现。

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    
    using namespace std;
    
    void print(vector < int > a, int n) {
        
      for (int i = 0; i < n; i++)
        cout << a[i] << " ";
      cout << endl;
    }
    
    // global dp array, size as per constraint, here n<=100000
    int arr[100001];
    
    // recursive solution
    int findmax(int n) {
        
      if (n <= 1)
        return n;
    
      int p = findmax(n / 2) + findmax(n / 3) + findmax(n / 4);
    
      return n > p ? n : p;
    }
    
    int main() {
        
      int t, n, item;
    
      // precompute the dp array
      arr[0] = 0;
      arr[1] = 1;
    
      for (int i = 2; i <= 100000; i++) {
        
        int p = arr[i / 4] + arr[i / 3] + arr[i / 2];
        arr[i] = i > p ? i : p;
      }
    
      cout << "Number of testcase:\n";
      scanf("%d", & t);
    
      for (int i = 0; i < t; i++) {
        
    
        cout << "Enter n\n";
        scanf("%d", & n);
    
        cout << "Maximum sum is: " << arr[n] << endl;
        // cout<<findmax(n)<<endl; 
        // if you want to check recursive one and have 
        // a long day to check for large n
      }
    
      return 0;
    }

**Output**

**输出量**

Number of testcase:
    2
    Enter n
    12
    Maximum sum is: 13
    Enter n
    24
    Maximum sum is: 27

> 翻译自: [https://www.includehelp.com/icp/maximum-sum-problem.aspx][https_www.includehelp.com_icp_maximum-sum-problem.aspx]

最大子矩阵和问题

[Maximum sum problem]: https://www.includehelp.com/icp/Images/maximum-sum-problem.jpg
[https_www.includehelp.com_icp_maximum-sum-problem.aspx]: https://www.includehelp.com/icp/maximum-sum-problem.aspx