You are not logged in. Please login at www.codechef.com to post your questions!

×

KCON - Editorial

Author: Hruday Pabbisetty
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

EASY

None

PROBLEM:

You are given array $A_0, \dots, A_{N-1}$ and integer $K$. Array $B$ of size $N \cdot K$ is formed by concatenating $K$ copies of array $A$. You have to find maximum subarray sum of the array $B$.

QUICK EXPLANATION

Answer is maximum sum subarray from doubled $A$ plus either $0$ or $K-2$ sums of all elements in $A$.

EXPLANATION:

Let's denote array $A$ concatenated with itself as $2A$. You should note that any subarray in array $B$ can be presented as arbitrary subarray in $2A$ plus from $0$ to $K-2$ whole arrays $A$. Indeed you begin in some position $i$, then swallow some whole number of arrays $A$ then continue from position which corresponds to $i+1$ in $2A$ and swallow at most $N-1$ elements, thus you won't leave array $2A$. So first of all you should find subarray with largest sum in $2A$, which you can do with prefix sums, Kadane's algorithm or any other algorithm you may find in this wikipedia article. After that if sum of elements in $A$ is positive, you add it with coefficient $K-2$, otherwise you add it with coefficient $0$. That gives you $O(N)$ solution.

Example of code to find maximum subarray sum:

const int64_t inf = 1e18;
int64_t sum = 0, mn = 0;
int64_t ans = -inf;
for(int i = 0; i < n; i++) {
sum += a[i];
ans = max(ans, sum - mn);
mn = min(mn, sum);
}
return ans;

With this code you can find the solution as follows:

if(k == 1) {
cout << maxsub(a) << endl;
} else {
int64_t sm = accumulate(begin(a), end(a), 0ll);
for(int i = 0; i < n; i++) {
a.push_back(a[i]);
}
int64_t ans = maxsub(a);
if(sm > 0) {
ans += sm * (k - 2);
}
cout << ans << endl;
}

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 11 Jan '18, 02:12

4★melfice
811937
accept rate: 0%

19.8k350498541

 1 how to calculate prefix and suffix and also what they mean answered 16 Jan '18, 16:10 0●1 accept rate: 0%
 0 Can someone please explain it in simple words? answered 15 Jan '18, 22:16 1★nikmul19 32●5 accept rate: 0%
 0 Would this not be able to calculate the maximum subarray sum too? dp[i] = max(dp[i-1]+arr2[i],arr2[i]+arr2[i-1]); answered 16 Jan '18, 06:58 1 accept rate: 0%
 0 Thanks @pazhamalai answered 16 Jan '18, 16:48 1★nikmul19 32●5 accept rate: 0%
 0 Author's solution is giving access denied answered 16 Jan '18, 20:24 1 accept rate: 0%
 0 what about when all numbers are zero consider -3 -1 -2 and k = 3 in this case what will be suffix and prefix? And according to the @pazhamalai explanation what should be the answer? answered 25 Jan '18, 21:13 1★cypher94 0 accept rate: 0%
 0 Try this test case 1 3 2 7 -8 4 answered 01 Jun '18, 16:49 5★vjvjain0 91●2●10 accept rate: 6%
 toggle preview community wiki:
Preview

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×191
×2
×2

question asked: 11 Jan '18, 02:12

question was seen: 3,019 times

last updated: 01 Jun '18, 16:49