fork(9) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. // Utility function to return maximum number present in given array
  5. int maximum(int arr[], int n)
  6. {
  7.     int res = arr[0];
  8.     for (int i = 1; i < n; i++)
  9.         res = max(res, arr[i]);
  10.  
  11.     return res;
  12. }
  13.  
  14. // Function to find contiguous sub-array with the largest sum
  15. // in given set of integers
  16. int kadane(int arr[], int n)
  17. {
  18.     // find maximum element present in given array
  19.     int max_num = maximum(arr, n);
  20.  
  21.     // if array contains all negative values, return maximum element
  22.     if (max_num < 0)
  23.         return max_num;
  24.  
  25.     // stores maximum sum sub-array found so far
  26.     int max_so_far = 0;
  27.  
  28.     // stores maximum sum of sub-array ending at current position
  29.     int max_ending_here = 0;
  30.  
  31.     // traverse the given array
  32.     for (int i = 0; i < n; i++)
  33.     {
  34.         // update maximum sum of sub-array "ending" at index i (by adding
  35.         // current element to maximum sum ending at previous index i-1)
  36.         max_ending_here = max_ending_here + arr[i];
  37.  
  38.         // if maximum sum is negative, set it to 0 (which represents
  39.         // an empty sub-array)
  40.         max_ending_here = max(max_ending_here, 0);
  41.  
  42.         // update result if current sub-array sum is found to be greater
  43.         max_so_far = max(max_so_far, max_ending_here);
  44.     }
  45.  
  46.     return max_so_far;
  47. }
  48.  
  49. // main function
  50. int main()
  51. {
  52.     int arr[] = { -8, -3, -6, -2, -5, -4 };
  53.     int n = sizeof(arr)/sizeof(arr[0]);
  54.  
  55.     cout << "The sum of contiguous sub-array with the largest sum is " <<
  56.             kadane(arr, n);
  57.  
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The sum of contiguous sub-array with the largest sum is -2
https://ideone.com/LPspSt
Find contiguous sub-array with the largest sum in given set of integers (Handle negative numbers)
language:
C++14 (gcc 8.3)
created:
7 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!