Convert this Python Kadane\'s algorithm to a C++ program : def max_subarray(A):
ID: 3677752 • 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
Answer for Given Question:
This below Program will convert the Kadane's algorthom to c++:
#include <iostream>
#include <climits>
using namespace std;
#define MAX(X, Y) (X > Y) ? X : Y
#define POS(X) (X > 0) ? X : 0
int maxSum = INT_MIN;
int N;
int kadane(int* row, int len)
{
int x, sum, maxSum = INT_MIN;
for (sum = POS(row[0]), x = 0; x < N; ++x, sum = POS(sum + row[x]))
maxSum = MAX(sum, maxSum);
return maxSum;
}
int main()
{
cout << "Enter the array length: ";
cin >> N;
int arr[N];
cout << "Enter the array: ";
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
cout << "The Max Sum is: "<<kadane(arr, N) << endl;
return 0;
}
Output:
Enter the array length: 5
Enter the array: 1 -5 2 -1 3
The Max Sum is: 4
Enter the array length: 9
Enter the array: -2 1 -3 4 -1 2 1 -5 4
The Max Sum is: 6