KCON - Help

Can anyone help with a counter testcase where my code fails ? Been thinking of this so long but couldn’t figure where I’m lagging and getting WA.

Problem : K-Concatenation
Solution :


using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define nl "\n" 

void solve(){
	int n,k;
	cin >> n >> k;
	int arr[n+1] {0};
	ll sum=0;
	for(int i=1;i<=n;++i){ 
		cin >> arr[i];
	const int INF = 1e6+5;
	ll maxSoFar=-INF;
	ll currsum=0;
	for(int i=1;i<=n;++i){
		currsum = max(maxSoFar+(ll)arr[i],(ll)arr[i]);
		maxSoFar = max(maxSoFar,currsum);
	ll ak = k*maxSoFar+(k-1)*(sum-maxSoFar);
	cout << max(maxSoFar,ak) << nl;
int main(){
    int t;//testcases
	return 0;

The logic behind the code is that we first find Maximum sum subarray. For k copies of the array we will have k*maxSoFar + few numbers in between each copy which we can choose to add or remove. The sum of those numbers are (k-1)*(sum-maxSoFar). We finally take the maximum of maxSoFar of a single array or the summed up value for k arrays.

Try out this test case:
5 3
1 -1 2 0 1
Correct answer: 9

Thanks bro. Caught the error :slight_smile: