First you need to figure how to write a proper function that will give you the maximum sum for any array.
If we start with a sample input
1, -2, 3, -2, 5, -1
you can use pen and paper to calculate the maximum sum for each sequence like this
Start Index = 0
0 + 1 = 1
1 - 2 = -1
-1 + 3 = 2
2 - 2 = 0
0 + 5 = 5 <- max
5 - 1 = 4
Start Index = 1
0 - 2 = -2
-2 + 3 = 1
1 - 2 = -1
-1 + 5 = 4 <- max
4 - 1 = 3
Start Index = 2
0 + 3 = 3
3 - 2 = 1
1 + 5 = 6 <- max and also maximum for the whole array
6 - 1 = 5
Start Index = 3
0 - 2 = -2
-2 + 5 = 3 <- max
3 - 1 = 2
Start Index = 4
0 + 5 = 5
5 - 1 = 4 <- max
Start Index = 5
0 - 1 = -1 <- max
Basically you loop through the array to find the maximum sum, then you increment the start index by 1 and find the maximum for the next sequence.
In code this can be done either by a double loop or recursively.
This is the recursive variant
int FindMaxValue(int* a, int len, int startIndex, int maxSum)
{
if (startIndex == len) return maxSum;
int currentMaxSum = maxSum;
int tempSum = 0;
for (int i = startIndex; i < len; i++)
{
tempSum += a[i];
if (tempSum > currentMaxSum )
currentMaxSum = tempSum;
}
return FindMaxValue(a, len, startIndex + 1, currentMaxSum);
}
In your main() you call the function like this:
int maxSum = FindMaxValue(a, n, 0, INT_MIN);
printf("Max sum: %d\r\n", maxSum);
The next task is to remove one of the numbers in the array and find the maximum value for the new array.
The easiest way to do this is to use yet another loop and exclude one number per iteration.
This requires a small modification of FindMaxValue() where you add the index you want to skip.
int FindMaxValue(int[] a, int len, int startIndex, int maxSum, int skipIndex)
{
if (startIndex == len)
return maxSum;
int currentMaxSum = maxSum;
int tempSum = 0;
for (int i = startIndex; i < len; i++)
{
if (i == skipIndex)
continue;
tempSum += a[i];
if (tempSum > currentMaxSum )
currentMaxSum = tempSum;
}
return FindMaxValue(a, len, startIndex + 1, currentMaxSum, skipIndex);
}
Add a new loop in the main function
int maxSum = 0;
for (int i = 0; i < a.Length; i++)
{
maxSum = FindMaxValue(a, n, 0, INT_MIN, i);
printf("Index = %d -> Max Sum = %d\r\n", i, maxSum);
}
If you want to get the actual sequence, you have to do that yourself.
At last, this code will not fly
long long int a[n];
you have to allocate memory dynamically
int* a = (int*)calloc(n, sizeof(int));
and don't forget to release the allocated memory at the end of the code
free(a);
Also, not sure who gave you the idea that you need to declare a
long long int
. That is just overkill with the requirements you show here.