将int数组拆分为3部分，最大化2个较小部分的大小

Question

给定int长度为n的数组，将数组拆分为3部分并确保2个较小部分尽可能大。

拆分规则：

• 挑两个指数a和给定阵列的b（0 < =一个< = B < = N-1）
• 第一部分的尺寸是：所有阵列的总和从索引0到a-1（含）的条目
• 第二部分的大小是：索引a到b（含）的所有数组条目的总和
• 第三部分的大小是：来自b + 1到n-1（包含IVE）
• 空零件是可能..

预期的输出是2个小的部分（它们的大小）的总和。例如，n = 6的数组和一些值被给出。 解决方案计算a = 2,b = 3，将阵列拆分为3部分：左侧部分大小为6 + 7 = 13，中间部分为8 + 9 = 17，右侧部分为4 + 5 = 9。输出是13 + 9 = 22（两个较小部分的总和）。

图形表示：

更多的例子：

[6,8，3，5，7，2，4，6]应被分成：

1. Left（6 + 8 = 14）
2. Middle（3 + 5 + 7 = 15）
3. 右（2 + 4 + 6 = 12）

的输出被14 + 12 = 26（2个小的部分的总和）

[9，12，4，7，10，2，5，8，11，3]应分成：

1. 左（9 + 12 + 4 = 25）
2. 中东（7 + 10 + 2 + 5 = 24）
3. 右（8 + 11 + 3 = 22）

输出是22 + 24 = 46（2个较小的部分的总和）

我的做法没有为给定的测试情况下工作：

// L is size of left part, M is size of middle part, R is size of right part 
/* I start with all array entries in the middle part, then I put elements 
    out of the middle part into the left and right part (depending on which 
    is smaller) until one of them is larger than M, this approach works for 
    many cases, two exceptions are the first 2 arrays given as examples in 
    this post. 
*/ 
     long a = 1; 
     long b = n; 
     long L = R = 0; 
     long M = arr.sumOfAllArrayEntries; 
     long temp; 
     long[] arr = {9, 12, 4, 7, 10, 2, 5, 8, 11, 3}; 

     while (M > Math.max(L, R)) { 
      if (L < R) { 
       // move leftmost element of M to L 
       temp = arr[(int) a++]; 

       M -= temp; 
       L += temp; 

      } 
      else { 
       // move rightmost element of M to R 
       temp = arr[(int) b--]; 

       M -= temp; 
       R += temp; 
      } 
     } 

     // finds maximum of M, L, R 
     temp = Math.max(M, Math.max(L, R)); 

     // finds 2 smallest numbers out of M, L, R 
     if (temp == M) 
      temp = L + R; 
     else if (temp == L) 
      temp = M + R; 
     else if (temp == R) 
      temp = M + L; 

     // temp is equal to the sum of the 2 smaller parts 
     System.out.println("Output: " + temp); 

Answer 1

浮现在脑海的基本思想是：在对a所有位置

• 循环。
  • 在b的所有位置循环。
    • 计算左，中，右总和。
    • 计算目标总和并将其存储，如果它比我们见过的最好总和好。

这可以通过注意一些事情进行优化，以O(n)：

• 对于任何给定的位置b，为a最好的位置永远是，和明智的，在b的中间和开始（特别是在最小化左边和中间和之间的差值处）。
• a的最佳位置不能向左移动，因为b向右移动（因为这会减少左边的总和以获得更大的中间值，从而减少目标总和）。
• 这意味着我们只需要一个循环而不是b，同时保持跟踪a，并在适当的时候增加。
• 我们可以随时跟踪款项。

这给了我们下面的代码：

int arr[] = {9, 12, 4, 7, 10, 2, 5, 8, 11, 3}; 
int sum = 0; 
for (int i: arr) 
    sum += i; 
int a = 0; 
int left = 0, mid = 0; 
int best = 0; 
for (int b = 0; b < arr.length; b++) 
{ 
    mid += arr[b]; 
    // since this loop increases `a` with every iteration, and `a` never resets, 
    // it will not run more than O(n) times in total 
    while (a < b && Math.min(left + arr[a], mid - arr[a]) > Math.min(left, mid)) 
    { 
     left += arr[a]; 
     mid -= arr[a]; 
     a++; 
    } 
    int right = sum - mid - left; 
    best = Math.max(best, 
        mid + left + right - Math.max(mid, Math.max(left, right))); 
} 
System.out.println(best); 

Live demo。

---

与方法的问题是，当你进入像一个情况：

 a  b 
6 7 | 8 9 | 4 5 
L=13 M=17 R=9 

M > Math.max(L, R)将是真实的，所以你会，移动的元素之一，尽管已经有最好的分裂。

请注意我在代码中做了Math.min(left + arr[a], mid - arr[a]) > Math.min(left, mid)而不是简单的left < mid。你需要类似的东西来检查你是否应该继续。

你需要考虑的一个例子是，你需要进一步增加更大方：

100 | 10 120 | 90 -> 100 10 | 120 | 90 

那可能你的代码相当多的复杂化。

Answer 2

这可以使用的Two Pointers概念来完成。所以首先看到主阵列连接3子数组。 A，B和C。现在我们可以首先计算数组中所有元素的总和，这表明所考虑的数组具有所有元素。

所以现在我们需要跟踪原始数组的3个连续子数组的总和。考虑在这里，我们这里有3个数组作为

A ---> Starting from the left-side (index 0) 
B ---> Middle sub-array 
C ---> Starting from the right-side (index n-1) 

这里的答案应该是min(sumOfA,min(sumOfB,sumOfC))这是最大化。

考虑到它具有数组的所有元素，这里我们已经存储了子数组B中所有元素的和。 A和C是空的。现在我们将从任一端删除一个元素，并将该值添加到适当的子数组A或C，我们需要通过减去它从B中删除它。

现在问题仍然是哪个元素将被删除。为此，我们将检查A和C的值以及总和低于其他值的任何人，我们将从该端添加元素到特定的子数组。

这里可能出现的另一个问题是终止条件。这里的终止条件是Sum of B > Sum of A && Sum of B > Sum of C。所以当B的总和小于其他两个子阵列的任何一个时，我们需要在那里停下来。

复杂性这种方法：O（n）的

代码：

import java.util.*; 

class Main 
{ 
    public static void main(String args[]) 
    { 
     long arr[]={9, 12, 4, 7, 10, 2, 5, 8, 11, 3}; 

     long sumOfA=0; 
     long sumOfB=0; 
     long sumOfC=0; 

     int a = 0;    //set end of sub-array A 
     int b = arr.length-1; //set start of sub-array-C 

     long maximum =0; // Minimum of sum of all subarrays should be maximum, 
         // That will be sufficient to get the answer 

     long answer=0; 
     int answer_a=0; 
     int answer_b=0; 

     for(int i=0;i<arr.length;i++) 
     { 
      sumOfB+=arr[i]; 
     } 

     for(int i=0;i<arr.length;i++) 
     { 
      long minimum = Math.min(sumOfA , Math.min(sumOfB,sumOfC)); 

      if(minimum>=maximum) 
      { 
       answer_a=a; 
       answer_b=b; 

       ArrayList<Long> list=new ArrayList<Long>();  //To calculate the answer 
       list.add(sumOfA); 
       list.add(sumOfB); 
       list.add(sumOfC); 
       Collections.sort(list); 

       answer=Math.max(answer,list.get(0)+list.get(1));   //take minimum two elements 
       maximum=minimum; 
      } 

      if(sumOfB < sumOfC || sumOfB < sumOfA) 
       break; 

      if(a>=b)    //If both pointer passes to each other 
       break; 

      if(sumOfA == sumOfC) 
      { 
       if(arr[a]<arr[b]) //take minimum element 
       { 
        sumOfA+=arr[a]; 
        sumOfB-=arr[a]; 
        a++;   //move a to next element 
       } 
       else 
       { 
        sumOfC+=arr[b]; 
        sumOfB-=arr[b]; 
        b--;   //move b to prev element 
       } 
      } 
      else if(sumOfA > sumOfC) 
      { 
       sumOfC+=arr[b]; 
       sumOfB-=arr[b]; 
       b--; 
      } 
      else 
      { 
       sumOfA+=arr[a]; 
       sumOfB-=arr[a]; 
       a++; 
      } 
     } 

     System.out.println("a(exclsive) : "+answer_a); 
     System.out.println("b(exclsive) : "+answer_b); 
     System.out.println("Answer : "+answer); 
    } 
} 

---

答案[9, 12, 4, 7, 10, 2, 5, 8, 11, 3]：

a(exclsive) : 3 
b(exclsive) : 6 
Answer : 46 

---

答案[6, 8, 3, 5, 7, 2, 4, 6]：

a(exclsive) : 2 
b(exclsive) : 4 
Answer : 26