fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. // Naive solution to find maximum sum subarray using
  5. // divide and conquer
  6. int maximum_sum(int A[], int n)
  7. {
  8.     int max_sum = INT_MIN;
  9.     int sum = 0;
  10.  
  11.     // do for each subarray starting with i
  12.     for (int i = 0; i < n - 1; i++)
  13.     {
  14.         // calculate sum of subarray A[i..j]
  15.  
  16.         sum = 0;    // reset sum
  17.  
  18.         // do for each subarray ending with j
  19.         for (int j = i; j < n; j++)
  20.         {
  21.             sum += A[j];
  22.  
  23.             // if current subarray sum is greater than the maximum sum
  24.             // calculated so far, update the maximum sum
  25.             if (sum > max_sum)
  26.                 max_sum = sum;
  27.         }
  28.     }
  29.  
  30.     return max_sum;
  31. }
  32.  
  33. // Maximum Sum Subarray using Divide & Conquer
  34. int main(void)
  35. {
  36.     int arr[] = { 2, -4, 1, 9, -6, 7, -3 };
  37.     int n = sizeof(arr) / sizeof(arr[0]);
  38.  
  39.     printf("The maximum sum of the subarray is %d", maximum_sum(arr, n));
  40.  
  41.     return 0;
  42. }
Success #stdin #stdout 0s 10320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The maximum sum of the subarray is 11
https://ideone.com/2MhqG6
Maximum Sum Subarray using Divide
language:
C (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!