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 :
#include<bits/stdc++.h>
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];
sum+=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(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;//testcases
cin>>t;
while(t--){
solve();
}
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.
