从给定数组中查找最低总和

Question

我有一个数字[3,4,5,1,2,3,1]查找3 Pairs sub sequence say sub [] sub [0]＆lt; sub [1]＆gt; sub [2]，总和这3个元素并获取最低总和。

示例：

对于[3,4,5,1,2,3,1]，我可以选择[1,2,1]这里1＆lt; 2＆gt; 1因此，总和是1+2+1 = 4最小。

约束：

数组尺寸最高1,00,000 每个元素大小为1至1,00,00,00,000

我的方法是使用3个嵌套进行循环，并获得最小总和，这不是有效的方法。

public long process(List<Integer> list) {
   int n = list.size();
   long output = Long.MAX_VALUE;
   for(int i=0; i<n; i++) {
      for(int j=i+1; j<n; j++) {
       if(list.get(i) < list.get(j)) {
          for(int k=j+1; k<n; k++) {
            if(list.get(j) > list.get(k)) {
               output = Math.min(output, list.get(i)+list.get(j)+list.get(k));
             }
          }
       }
      }
   }
   return output;
}

如何以较小的时间复杂性有效地解决该程序？

Answer 1

让我提供一个解决方案，其时间复杂性为o（n），空间复杂性为o（n）。您必须通过三次阵列迭代，并存储两个阵列以达到最低元素。我受到@SomeOne的评论的启发。请记住，该解决方案可以假设任何sub [i]＆lt; sub [j]＆gt; sub [k]必须保持：i＆lt; J＆LT; k。

可以轻松修改解决方案以覆盖i＆lt; = j＆lt; = k的情况。如果该方程式没有强制性，那么问题就会变得更加琐碎。只需找到前三个最小元素，我们知道sub [i]＆lt; sub [j]＆gt; sub [k]保持。确保第三个（最大）与其他一个不同。尽管您没有指定我上面提到的规则，但我相信问题要您遵守该规则 - 否则这将非常微不足道。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Stackoverflow {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3,4,5,1,2,3,1));
        System.out.println(process(numbers));
    }
    
    public static long process(List<Integer> list) {
        if(list.size() < 3) return -1; // not enough elements
        
        int n = list.size();
        
        int[] minLeft = new int[n];
        int[] minRight = new int[n];
        
        minLeft[0] = list.get(0);
        minRight[minRight.length - 1] = list.get(list.size() - 1);
        
        // store the minimum elements from left up to current index
        for(int i=1; i<n; i++) {
            minLeft[i] = Math.min(list.get(i), minLeft[i - 1]);
        }
        
        
        // store the maximum elements from right up to current index
        for(int i=n - 2; i>=0; i--) {
            minRight[i] = Math.min(list.get(i), minRight[i+1]);
        }
        
        
        long sum = Integer.MAX_VALUE;
        
        for(int i=1; i<n-1; i++) {
            sum = Math.min(sum, minLeft[i - 1] + list.get(i) + minRight[i + 1]);
        }
        
        return sum;
    }
}

输出：

4

Answer 2

相同的代码和添加的次要约束以考虑角案例：

public class minimumSubsequence {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3, 4, 5, 1, 2, 3, 1));
        System.out.println(minimumSubsequence.getMinimumSum(numbers));
    }

    public static long getMinimumSum(List<Integer> arr) {
        if (arr.size() < 3)
            return -1;

        int n = arr.size();
        int[] minLeft = new int[n];
        int[] minRight = new int[n];
        minLeft[0] = arr.get(0);
        minRight[n - 1] = arr.get(arr.size() - 1);

        //find min from left
        for (int i = 1; i < n; i++) {
            minLeft[i] = Math.min(arr.get(i), minLeft[i - 1]);
        }
        // find min from right
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.min(arr.get(i), minRight[i + 1]);
        }

        long sum = Integer.MAX_VALUE;
        int flag = 0;
        for (int i = 1; i < n - 1; i++) {
            if (minLeft[i - 1] < arr.get(i) && minRight[i + 1] < arr.get(i)) {
                sum = Math.min(sum, minLeft[i - 1] + arr.get(i) + minRight[i + 1]);
                flag = 1;
            }
        }
        if (flag == 0) return -1;
        return sum;

    }

}