Guest User

Untitled

a guest
Sep 15th, 2019
80
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