SHARE
TWEET

Untitled

a guest Sep 15th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         if (nums.empty()) {
  5.             // invalid input
  6.             return -1;
  7.         }
  8.         int i = 0;
  9.         int j = 1;
  10.         int currentSum = nums[0];
  11.         int maxSoFar = currentSum;
  12.         while (i < nums.size() && j < nums.size()) {
  13.             // decide whether to do one of three options:
  14.             // add the jth element to your running sum
  15.             // don't add the jth element to your running sum
  16.             // start a new subarray starting from j
  17.             if (currentSum+nums[j] > nums[j]) {
  18.                 currentSum = currentSum + nums[j];
  19.             } else {
  20.                 i = j;
  21.                 currentSum = nums[j];
  22.             }
  23.             maxSoFar = std::max(maxSoFar, currentSum);
  24.             j++;
  25.  
  26.         }
  27.         return maxSoFar;
  28.     }
  29. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top