Convert this Python Kadane\'s algorithm to a C++ program : def max_subarray(A):
ID: 3677710 • 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++ refrences to return the values. Do not use (return, array , object or any other ways to return the values of these three varibals).
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
// C++ program to print largest contiguous array sum
#include<iostream>
using namespace std;
void kadane(int A[], int N, int& bestStart, int& bestEnd, int& bestSum){
int max_so_far = A[0], max_ending_here = A[0];
for (int i = 0; i < N; i++){
if (max_ending_here < 0){
max_ending_here = A[i];
bestStart = i;
}
else
max_ending_here += A[i];
if (max_so_far < max_ending_here){
max_so_far = max_ending_here;
bestEnd = i;
}
}
bestSum = max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int start,end,sum;
int n = sizeof(a)/sizeof(a[0]);
kadane(a, n, start, end, sum);
cout << "Maximum contiguous sum is " << sum<<" starting at "<<start <<" and ending at "<<end; ;
return 0;
}