fork(4) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. // Function to print contiguous subarray with the largest sum
  5. // in given set of integers
  6. void kadane(int arr[], int n)
  7. {
  8.     // stores maximum sum subarray found so far
  9.     int max_so_far = arr[0];
  10.  
  11.     // stores maximum sum of subarray ending at current position
  12.     int max_ending_here = arr[0];
  13.  
  14.     // stores end-points of maximum sum subarray found so far
  15.     int start = 0, end = 0;
  16.  
  17.     // stores starting index of a positive sum sequence
  18.     int beg = 0;
  19.  
  20.     // traverse the given array
  21.     for (int i = 1; i < n; i++)
  22.     {
  23.         // update maximum sum of subarray "ending" at index i
  24.         max_ending_here = max_ending_here + arr[i];
  25.  
  26.         // if maximum sum is negative, set it to 0
  27.         if (max_ending_here < arr[i])
  28.         {
  29.             max_ending_here = arr[i];    // empty subarray
  30.             beg = i ;
  31.         }
  32.  
  33.         // update result if current subarray sum is found to be greater
  34.         if (max_so_far < max_ending_here)
  35.         {
  36.             max_so_far = max_ending_here;
  37.             start = beg;
  38.             end = i;
  39.         }
  40.     }
  41.  
  42.     cout << "The sum of contiguous subarray with the largest sum is " <<
  43.             max_so_far << endl;
  44.  
  45.     cout << "The contiguous subarray with the largest sum is ";
  46.     for (int i = start; i <= end; i++)
  47.         cout << arr[i] << " ";
  48. }
  49.  
  50. // main function
  51. int main()
  52. {
  53.     int arr[] = { -2, -1, -3, -4, -1, -2, -1, -5, -4 };
  54.     int n = sizeof(arr)/sizeof(arr[0]);
  55.  
  56.     kadane(arr, n);
  57.  
  58.     return 0;
  59. }
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The sum of contiguous subarray with the largest sum is -1
The contiguous subarray with the largest sum is -1
https://ideone.com/chOUZq
Print contiguous subarray with the largest sum
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!