Trying to solve https://leetcode.com/problems/k-concatenation-maximum-sum/submissions/, I still got integer overflow when the data type is long
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int max(int a, int b) {
return a > b ? a : b;
}
int sum(int *nums, int numSize) {
int ans = 0;
for (int i = 0; i < numSize; ++i)
ans += nums[i];
return ans;
}
int KandaneAlgo(int *nums, int numSize) {
int i, max_overall_so_far = 0, max_ending_here = 0;
for (i = 0; i < numSize; ++i) {
max_ending_here += nums[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_overall_so_far < max_ending_here)
max_overall_so_far = max_ending_here;
}
return max_overall_so_far;
}
int kConcatenationMaxSum(int *arr, int arrSize, int k) {
int mod = pow(10, 9) + 7;
int ans;
if (k > 1) {
long tem = (k - 2) * max(sum(arr, arrSize), 0);
int t1 = tem % mod;
printf("%ld, %d, %d \n", tem, t1, mod);
int arr2[2 * arrSize];
for (int i = 0; i < 2 * arrSize; ++i)
arr2[i] = arr[i - i / arrSize * arrSize];
ans = (int)t1 + KandaneAlgo(arr2, 2 * arrSize) % mod;
} else {
ans = KandaneAlgo(arr, arrSize) % mod;
}
return ans;
}
int main() {
int arr[10] = { [0 ... 9] = 10000 };
for (int i = 0; i < 10; ++i)
printf("%d ", arr[i]);
printf("\n");
int tot = kConcatenationMaxSum(arr, 10, 100000);
printf("%d \n", tot);
return 0;
}
I locally debug with lldb and can see the output message of variable tem is wrong indeed, it should be 9999800000.