Why i am getting wrong output in sample case ?
2
2 3
1 2
3 2
1 -2 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>
#include <cmath>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
typedef long long int ll;
void print2dArr(ll **arr,ll rows,ll cols){
for(ll i=0;i<rows;i++){
for(ll j=0;j<cols;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
ll kadane(ll *arr,ll n){
ll currSum=0;
ll maxSofar=INT_MIN;
for(ll i=0;i<n;i++){
currSum+=arr[i];
if(maxSofar<currSum){
maxSofar=currSum;
}
if(currSum<0){
currSum=0;
}
}
return maxSofar;
}
ll MaxSubSum(ll *arr,ll n,ll k){
ll kadaneSum=kadane(arr,n);
if(k==1){
return kadaneSum;
}
ll currPrefixSum=0;
ll currSuffixSum=0;
ll maxPrefixSum=INT_MIN;
ll maxSuffixSum=INT_MIN;
for(ll i=0;i<n;i++){
currPrefixSum+=currPrefixSum+arr[i];
maxPrefixSum = max(currPrefixSum,maxPrefixSum);
}
ll totalSum=currPrefixSum;
for(ll i=n-1;i>=0;i--){
currSuffixSum=currSuffixSum+arr[i];
maxSuffixSum=max(maxSuffixSum,currSuffixSum);
}
ll res=0;
if(totalSum<0){
res=max(maxSuffixSum+maxPrefixSum,kadaneSum);
}
else{
res=max(maxPrefixSum+maxSuffixSum+(totalSum*(k-2)),kadaneSum);
}
return res;
}
void solve(){
ll n,k;
cin>>n>>k;
ll *arr=new ll[n];
for(ll i=0;i<n;i++) {
cin>>arr[i];
}
cout<<MaxSubSum(arr,n,k)<<endl;
}
int main() {
fastio;
ll t=1;
cin>>t;
while(t--){solve();}
return 0;
}