求数组的最大反转和

Question

您将获得一个 0 索引的数组

vect

，其中包含

个整数。您需要执行以下 2 个操作一次 -

选择索引
```
i
```
{0, 1, 2, ..., n-1} 并将整个 前缀段 {0..i} 乘以 -1。
选择索引
```
j
```
{0, 1, 2, ..., n-1} 并将整个 后缀段 {j...n-1} 乘以 -1。

选择

和

，我们需要最大化数组所有元素的总和。

注：
前缀和后缀段可能会重叠，即当

i = j

或 i > j
时。正如预期的那样，当一个子段经历这两种操作时，它的价值保持不变。

方法：

使数组从 1 开始并计算前缀
```
pref
```
和后缀
```
suff
```
和。
在计算任意索引
```
i
```
和
```
j
```
处的最大总和（其中 i < j
）时，我们有
```
sum = (-1)*pref[i] + Z + (-1)*suff[j]
```
Z 可以计算为
```
pref[j-1] - pref[(i+1)-1]
```
。
```
Z = {}
```
当
```
j - i = 1
```
时。
我们只能有
```
j > i
```
，因为重叠的子段将保持不变，并且对最终答案没有影响。
迭代不同的
```
i
```
和
```
j
```
值。

时间复杂度 -

O(n^2)

观察

如果
```
pref
```
中没有一个元素为负数，我们只能对
```
pref[1]
```
取负，尽可能减少最大和。同样，对于
```
suff
```
，我们可以做
```
suff[n]
```
。
如果
```
pref
```
和
```
suff
```
中至少有一个元素为负，比如说
```
pref[i] < 0
```
和
```
suff[j] < 0
```
，我们的最大答案将始终涉及否定
```
pref[i]
```
或
```
suff[j]
```
或两者都否定（如果
```
i < j
```
）。

我们可以使用上述观察结果进行轻微的优化，但这不会改变时间复杂度（

vect

中的所有元素都是负数的情况，导致

pref

和

suff

都有负数元素）。

代码（C++）

using ll = long long;

ll getMaxInvSum(vector<int> vect) {
    int n = vect.size();
    
    vector<ll> pref(n+2), suff(n+2); // add dummy element at the front and back of vect
    
    pref[0] = 0;
    for(int i=0; i<n; i++) pref[i+1] = pref[i] + vect[i];
    pref[n+1] = pref[n]; 
    
    suff[n+1] = 0;
    for(int j=n-1; j>=0; j--) suff[j+1] = suff[j+2] + vect[j];
    suff[0] = suff[1];
    
    ll ans = pref[n]; // pref[n+1], suff[0], suff[1]
    
    for(int i=1; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(j-i == 1) 
                ans = max(ans, pref[i]*(-1) + suff[j]*(-1));
            else
                ans = max(ans, pref[i]*(-1) + suff[j]*(-1) + pref[j-1] - pref[i+1-1]);
        }
    }
    
    return ans;
}

如何提高时间复杂度？

Answer 1

调用输入向量 A 并解析一次，跟踪最小前缀和和索引，比如 i，即达到最小值的位置。

然后，反向执行相同操作，找到最小后缀和以及达到最小值的索引（例如 j）。

最后，将 A[0, ..., i] 乘以 -1，将 A[j, ..., n-1] 乘以 -1。

如果允许前缀/后缀为空，则当最小前缀/后缀和为正时将其留空。

Ruby 代码（读为伪代码；不懂 C++）

def f(arr)
  n = arr.length
  min_prefix_sum = 0
  cur_prefix_sum = 0
  min_prefix_index = -1
  0.upto(n-1) do |i|
    cur_prefix_sum += arr[i]
    if cur_prefix_sum < min_prefix_sum
      min_prefix_sum = cur_prefix_sum
      min_prefix_index = i
    end
  end
  
  min_suffix_sum = 0
  cur_suffix_sum = 0
  min_suffix_index = n
  (n-1).downto(min_prefix_index+2) do |i|
    cur_suffix_sum += arr[i]
    if cur_suffix_sum < min_suffix_sum
      min_suffix_sum = cur_suffix_sum
      min_suffix_index = i
    end
  end
  
  puts "prefix: [0, #{min_prefix_index}], suffix: [#{min_suffix_index}, #{n-1}]"
  puts "input arr: #{arr.to_s}"
end

以下是一些输入/输出：

input arr: [-3, 40, -44, 16, -15, 18, -44, 15, -48, 44, -16, 38, 22, 6, -4, -10, 1, -1, 14, 23]
prefix: [0, 8], suffix: [20, 19]

input arr: [29, 47, -17, -50, 22, 42, 5, 22, -17, 19, -23, 17, 0, 1, -44, 2, 45, 5, -42, 47]
prefix: [0, -1], suffix: [20, 19]

input arr: [30, 43, -36, -22, 16, 8, 9, -4, 16, 16, -21, -24, 13, 20, 27, -1, -12, 20, -11, 47]
prefix: [0, -1], suffix: [20, 19]

input arr: [-35, -49, -4, 32, -37, -6, 13, 18, 20, -29, -8, 5, -49, 28, 44, 36, 3, 13, 47, -35]
prefix: [0, 12], suffix: [19, 19]

input arr: [-39, -13, -34, 1, -33, -50, 6, 33, -20, -30, -7, 37, -48, -22, 32, 1, 24, -9, -9, -39]
prefix: [0, 13], suffix: [17, 19]

^^ 请注意，如果前缀为 [0,-1] 或后缀为 [n, n-1]，则前缀/后缀应为空。如果要求非空，我们可以轻松修改它来处理它。

求数组的最大反转和

问题描述投票：0回答：1

1个回答

最新问题

求数组的最大反转和

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1