Thursday, 14 September 2017

Sum of Maximum SubArray O(n) Time Complexity Short Code (C++)

//Find the maximum sum of subarray
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
n=8; //size of array
int arr[] ={-2,-3,4,-1,-2,1,5,-3};
int best= 0, sum =0;
for(int i=0;i<n;i++){
sum = max(arr[i],sum+ arr[i]);  // max of array
best= max(best,sum);  // Largest sum of subarray

}
cout<< best<<"\n";


return 0;
}

No comments:

Post a Comment

Spoj Problem ACMCEG2C - Pick the candies (C++)

  The problem link may be found here.       Explanation: Use Deque to keep track of elements of the variety of candies. If i is gre...