Convert this Python Kadane\'s algorithm to a C++ program : def max_subarray(A):
ID: 3677749 • Letter: C
Question
Convert this Python Kadane's algorithm to a C++ program :
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
Requirements:
1- There is another version of the Kadane's algorithm, make sure you are using the above version in which the max_ending_here and max_so_far start from A[0]
2- For the output you must return the start index , end index and the sum of the maximum subarray
3- use C++ references to return the values. Do not use (return, array , object or any other ways to return the values of these three variables).
4- Here is the head of the method that you should follow: void kadane(int A[], int N, int& bestStart, int& bestEnd, int& bestSum).
Explanation / Answer
Program 1:
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout << "Maximum contiguous sum is " << max_sum;
return 0;
}
program 2: