CODEWITHSUNDEEP
arraysalgorithm
Agnishom Chattopadhyay
Agnishom Chattopadhyay

Reputation: 2041

Largest Slice Sum from Two Different Arrays

Original Problem: Problem 1 (INOI 2015)

There are two arrays A[1..N] and B[1..N]

An operation SSum is defined on them as

The challenge is to find the largest possible value of SSum.

I had an O(n^2) solution based on computing the Prefix Sums of B

#include <iostream>
#include <utility>

int main(){
  int N;
  std::cin >> N;

  int *a = new int[N+1];
  long long int *bPrefixSums = new long long int[N+1];

  for (int iii=1; iii<=N; iii++) //1-based arrays to prevent confusion
    std::cin >> a[iii];
  bPrefixSums[0] = 0;
  for (int b,iii=1; iii<=N; iii++){
    std::cin >> b;
    bPrefixSums[iii] = bPrefixSums[iii-1] + b;
  }

  long long int SSum, SSumMax=-(1<<10);

  for (int i=1; i <= N; i++)
    for (int j=1; j <= N; j++){
      if (i<j)
        SSum = a[i] + a[j] + (bPrefixSums[j-1] - bPrefixSums[i]);
      else if (i==j)
        SSum = a[i];
      else
        SSum = a[i] + a[j] + ((bPrefixSums[N] - bPrefixSums[i]) + bPrefixSums[j-1]);
      SSumMax = std::max(SSum, SSumMax);
    }

  std::cout << SSumMax;

  return 0;
}

For larger values of N around 10^6, the program fails to complete the task in 3 seconds.

Upvotes: 0

Views: 87

Answers (1)

SCaffrey
SCaffrey

Reputation: 341

Since I didn't get enough rep to add a comment, I shall just write the ideas here in this answer.

This problem is really nice, and I was actually inspired by this link. Thanks to @superty.

We may consider this problem separately, in other words, into three conditions: i == j, i < j, i > j. And we only need to find the maximum result.

Consider i == j: The maximum result should be a[i], and it's easy to find the answer in O(n) time complexity.

Consider i < j: It's quite similar to the classical maximum sum problem, and for each j we only need to find the i in the left which manages to make the result maximum.

Think about the classical problem first, if we are asked to get the maximum partial sum for array a, we calculate the prefix-sum of a in order to get an O(n) complexity. Now in this problem, it is almost the same.

You can see that here(i < j), we have SSum[i,j] = A[i] + A[j] + B[t (where t = i+1, i+2, ..., j-1)] = (B[1] + B[2] + ... + B[j - 1] + A[j]) - (B[1] + B[2] + ... B[i] - A[i]), and the first term stays the same when j stays the same while the second term stays the same when i stays the same. So the solution now is quite clear, you get two 'prefix-sum' and find the smallest prefix_sum_2[i] for each prefix_sum_1[j].

Consider i > j: It's quite similar with this discussion on SO(but this discussion doesn't help much).

Similarly, we get SSum[i,j] = A[i] + A[j] + B[t (where t = 1, 2, ..., j-1, i+1, i+2, ..., N)] = (B[1] + B[2] + ... + B[j - 1] + A[j]) + (A[i] + B[i + 1] + ... + B[n - 1] + B[n]). Now you need to get both the prefix-sum and the suffix-sum of the array (we need prefix_sum[i] = a[i] + prefix_sum[i - 1] - a[i - 1] and suffix similarly), and get another two arrays, say ans_left[i] as the maximum value of the first term for all j <= i and ans_right[j] as the maximum value of the second term for i >= j, so the answer in this condition is the maximum value among all (ans_left[i] + ans_right[i + 1])

Finally, the maximum result required for the original problem is the maximum of the answers for these three sub-cases.

It's clear to see that the total complexity is O(n).

Upvotes: 1

Related Questions