fork(1) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int get_largest_sum(int a[], int n, int& start, int& end)
  5. {
  6.     int start_temp;
  7.     int curr_max = a[0],max_so_far = a[0];
  8.     start = end = 0;
  9.  
  10.     for(int i = 1; i < n; i++)
  11.     {
  12.         if (a[i] > curr_max + a[i])
  13.         {
  14.             curr_max = a[i];
  15.  
  16.             if(curr_max > 0) //to handle the case when all elements are negative
  17.                 start = i;
  18.         }
  19.         else
  20.             curr_max = curr_max + a[i];
  21.         if (max_so_far <= curr_max)
  22.         {
  23.             max_so_far = curr_max;
  24.             end = i;
  25.  
  26.             if (max_so_far < 0) //to handle the case when all elements are negative
  27.                 start = i;
  28.         }
  29.     }
  30.  
  31.     return max_so_far;
  32. }
  33.  
  34. int main()
  35. {
  36.     //int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  37.     int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
  38.     //int a[] = {-2, -3, -1, -2, -3};
  39.     int n = sizeof(a)/sizeof(a[0]);
  40.  
  41.     int start, end;
  42.     int sum = get_largest_sum(a, n, start, end);
  43.  
  44.     printf("Sum = %d...Start index = %d...End index = %d", sum, start, end);
  45.     getchar();
  46. }
Success #stdin #stdout 0s 2688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sum = 7...Start index = 2...End index = 6
https://ideone.com/2Mhplo
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years ago
visibility:
public

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!