Advertisement
STANAANDREY

min/max subarrsum

Oct 7th, 2019
248
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. int maxSubArrSum(int v[], int n)
  5. {
  6.     int maxi = INT_MIN, currmax = 0;
  7.     bool haspos = false;
  8.     for (int i = 0; i < n; i++)//daca nu exista elem pozitiv
  9.     {
  10.         maxi = max(maxi, v[i]);
  11.         if (v[i] > 0)
  12.             haspos = true;
  13.         if (!haspos && i == n - 1)
  14.             return maxi;
  15.     }
  16.  
  17.     maxi = INT_MIN;
  18.     for (int i = 0; i < n; i++)
  19.     {
  20.         currmax += v[i];
  21.         if (currmax < 0)
  22.             currmax = 0;
  23.         else if (currmax > maxi)
  24.             maxi = currmax;
  25.     }
  26.  
  27.     return maxi;
  28. }
  29.  
  30. int minSubArrSum(int v[], int n)
  31. {
  32.     int mini = INT_MAX, currmin = 0;
  33.  
  34.     bool hasneg = false;
  35.     for (int i = 0; i < n; i++)
  36.     {
  37.         mini = min(mini, v[i]);
  38.         if (v[i] < 0)
  39.             hasneg = true;
  40.         if (!hasneg && i == n - 1)
  41.             return mini;
  42.     }
  43.  
  44.     mini = INT_MAX;
  45.     for (int i = 0; i < n; i++)
  46.     {
  47.         currmin += v[i];
  48.         if (currmin > 0)
  49.             currmin = 0;
  50.         else if (currmin < mini)
  51.             mini = currmin;
  52.     }
  53.  
  54.     return mini;
  55. }
  56.  
  57. int main()
  58. {
  59.     int v[]{8 ,-5 ,1 ,-3 ,7 ,-3 ,2 ,8 ,-3 ,1}, n = 10;
  60.     cout << maxSubArrSum(v, n) << endl << minSubArrSum(v, n);
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement