Users Online

· Guests Online: 113

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Implement Kadane?s Algorithm

C++ Program to Implement Kadane?s Algorithm

C++ Program to Implement Kadane’s Algorithm

This is a C++ Program to Implement Kadane Algorithm. Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers.

Here is source code of the C++ Program to Implement Kadane’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#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:

$ g++ Kadane.cpp
$ a.out
 
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
 
------------------
(program exited with code: 0)
Press return to continue

Comments

No Comments have been Posted.

Post Comment

Please Login to Post a Comment.

Ratings

Rating is available to Members only.

Please login or register to vote.

No Ratings have been Posted.

Render time: 0.69 seconds

10,267,874 unique visits