如何从给定数组中找到子集的最大总和。 （子集的元素不能大于任何 2 个元素的总和）
How to find the largest sum of the subset from a giving array. (Subset can't not have element greater than sum of any 2 elements)
我 运行 在我的编码面试中遇到了一个感兴趣的挑战。我需要帮助找到另一种更好的方法来解决问题。
问题：给出一个有 N 个元素的数组。
我们需要return满足以下条件的子集的最大总和。
条件：子集中任意元素不能大于子集中任意2个元素之和
子集可以有 0 到 N 个元素。如果子集有1到2个元素(不需要遵循条件)
示例：
N = [10,4,4,4,5]
结果为4+4+4+5 = 17。输出为17
*注意：我们只需要return求和（不需要return子集）
第二个例子
N = [100,99,98,4,4,4,4,4,5]
结果将是100+99+98。输出为 297
我的解决方案：
我找到所有可能的子集，然后我找到满足条件的任何子集的总和。
然后我找到子集的最大总和
n = [100,4,4,4,5]
def findPossibleSum(n):
n.sort() #I sort the n so that it can be easier to check the condition later
result_temp = 0
result = max(n) #for situation that largest sum belong to 1 element subarray.
for i in range(0,len(n)+1):
for j in range(i+1,len(n)+1): #find all subset
if len(n[i:j]) == 2: #check subset that have 2 elements
result_temp = sum(n[i:j])
if len(n[i:j]) > 2: #subset that have more then 2 elements
if n[j-1] < (n[i] + n[i+1]): #Because I sort the n from beginning. Now that I can check the largest elements(which is the one on the right side) and the sum of smallest elements(2 on the left side).(to determine the condition)
result_temp = sum(n[i:j])
else:
pass
if result_temp > result:
result = result_temp
return(result)
我的问题：我的解决方案的时间复杂度 > O(N^3)。有没有办法在 O(N) 或 O(N^2) 中解决这个问题。
这是一个复杂度为 O(n log n) 的算法，不可能比 O(n log n) 做得更好，因为您需要先对数组进行排序。排序后，您可以在 O(n) 中完成剩余的工作。
观察 1
考虑满足条件的子集 S 至少有 3 个元素。然后所有包含数组 A 中位于 min(S) 和 max(S)[=52 之间的数字的子集=]也满足条件。因此没有必要考虑数组 A 的所有子集。将A按降序排序就足够了，只考虑排序的A的子数组.
观察 2
如果满足以索引i开头的条件的最长子数组长度为k，那么为了找到以索引j > i开头且满足条件[=42]的子数组=] 和 的总和大于第一个子数组，仅考虑长度 > k 的子数组就足够了，因为所有其他子数组的总和都较小。这意味着我们只需要考虑 O(n) 个候选子数组。
观察 3
如果满足以索引i开始的条件的最长子数组长度为k，其和为x，则子数组的和开始索引 i+1 长度 k 是 x - A[i] + A[i + k + 1]，所以下一个候选子数组的总和总是可以在常数时间内计算出来。
算法 (C#)
int findMaxSum(int[] array)
{
if (array.Length == 0) return 0;
Array.Sort(array);
Array.Reverse(array);
int k = 0;
int maxSum = 0;
int currentSum = array[0];
for (int i = 0; i < array.Length; i++)
{
// find the longest subarray starting from i
while (i + k + 1 < array.Length)
{
if (k > 0 && array[i] > array[i + k] + array[i + k + 1])
{
// condition not satisfied, so we've found the longest subarray
k = k - 1;
break;
}
// grow the subarray and increase the current sum
k = k + 1;
currentSum = currentSum + array[i + k];
}
// check if the sum of the longest subarray starting from i is larger than the largest sum found so far
maxSum = Math.Max(maxSum, currentSum);
// subtract the first element to consider subarrays starting from i + 1
currentSum = currentSum - array[i];
}
return maxSum;
}
复杂性
对数组进行排序是 O(n log n)。之后，我们将增长一个滑动子数组，其长度会递增，直到不再满足条件，并且它会从左向右滑动，直到到达数组的末尾。因此，尽管有嵌套循环，这需要 O(n).
所以整体复杂度为 O(n + n log n) = O(n log n)。
我 运行 在我的编码面试中遇到了一个感兴趣的挑战。我需要帮助找到另一种更好的方法来解决问题。
问题：给出一个有 N 个元素的数组。
我们需要return满足以下条件的子集的最大总和。
条件：子集中任意元素不能大于子集中任意2个元素之和
子集可以有 0 到 N 个元素。如果子集有1到2个元素(不需要遵循条件)
示例： N = [10,4,4,4,5]
结果为4+4+4+5 = 17。输出为17
*注意：我们只需要return求和（不需要return子集）
第二个例子
N = [100,99,98,4,4,4,4,4,5]
结果将是100+99+98。输出为 297
我的解决方案：
我找到所有可能的子集，然后我找到满足条件的任何子集的总和。 然后我找到子集的最大总和
n = [100,4,4,4,5]
def findPossibleSum(n):
n.sort() #I sort the n so that it can be easier to check the condition later
result_temp = 0
result = max(n) #for situation that largest sum belong to 1 element subarray.
for i in range(0,len(n)+1):
for j in range(i+1,len(n)+1): #find all subset
if len(n[i:j]) == 2: #check subset that have 2 elements
result_temp = sum(n[i:j])
if len(n[i:j]) > 2: #subset that have more then 2 elements
if n[j-1] < (n[i] + n[i+1]): #Because I sort the n from beginning. Now that I can check the largest elements(which is the one on the right side) and the sum of smallest elements(2 on the left side).(to determine the condition)
result_temp = sum(n[i:j])
else:
pass
if result_temp > result:
result = result_temp
return(result)
我的问题：我的解决方案的时间复杂度 > O(N^3)。有没有办法在 O(N) 或 O(N^2) 中解决这个问题。
这是一个复杂度为 O(n log n) 的算法，不可能比 O(n log n) 做得更好，因为您需要先对数组进行排序。排序后，您可以在 O(n) 中完成剩余的工作。
观察 1
考虑满足条件的子集 S 至少有 3 个元素。然后所有包含数组 A 中位于 min(S) 和 max(S)[=52 之间的数字的子集=]也满足条件。因此没有必要考虑数组 A 的所有子集。将A按降序排序就足够了，只考虑排序的A的子数组.
观察 2
如果满足以索引i开头的条件的最长子数组长度为k，那么为了找到以索引j > i开头且满足条件[=42]的子数组=] 和 的总和大于第一个子数组，仅考虑长度 > k 的子数组就足够了，因为所有其他子数组的总和都较小。这意味着我们只需要考虑 O(n) 个候选子数组。
观察 3
如果满足以索引i开始的条件的最长子数组长度为k，其和为x，则子数组的和开始索引 i+1 长度 k 是 x - A[i] + A[i + k + 1]，所以下一个候选子数组的总和总是可以在常数时间内计算出来。
算法 (C#)
int findMaxSum(int[] array)
{
if (array.Length == 0) return 0;
Array.Sort(array);
Array.Reverse(array);
int k = 0;
int maxSum = 0;
int currentSum = array[0];
for (int i = 0; i < array.Length; i++)
{
// find the longest subarray starting from i
while (i + k + 1 < array.Length)
{
if (k > 0 && array[i] > array[i + k] + array[i + k + 1])
{
// condition not satisfied, so we've found the longest subarray
k = k - 1;
break;
}
// grow the subarray and increase the current sum
k = k + 1;
currentSum = currentSum + array[i + k];
}
// check if the sum of the longest subarray starting from i is larger than the largest sum found so far
maxSum = Math.Max(maxSum, currentSum);
// subtract the first element to consider subarrays starting from i + 1
currentSum = currentSum - array[i];
}
return maxSum;
}
复杂性
对数组进行排序是 O(n log n)。之后，我们将增长一个滑动子数组，其长度会递增，直到不再满足条件，并且它会从左向右滑动，直到到达数组的末尾。因此，尽管有嵌套循环，这需要 O(n).
所以整体复杂度为 O(n + n log n) = O(n log n)。