# 53. Maximum Subarray
Difficulty: Easy

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-09-30
**/
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;
#include <vector>
using std::vector;

struct TestCaseStruct {
  vector<int> input;
  int output;
};

class Solution {
 public:
  int maxSubArray(vector<int> &nums) {
    int max_sum = INT_MIN;
    int sum = 0;

    for (const auto &num : nums) {
      sum += num;
      max_sum = std::max(max_sum, sum);
      if (sum < 0) {
        sum = 0;
      }
    }

    return max_sum;
  }
};

int main(int argc, char *argv[]) {
  vector<TestCaseStruct> test_cases = {{{-2, 1, -3, 4, -1, 2, 1, -5, 4}, 6},
                                       {{1}, 1},
                                       {{0}, 0},
                                       {{-1}, -1},
                                       {{-2147483647}, -2147483647}};

  int case_index = 0;
  Solution solution;
  for (auto &test_case : test_cases) {
    if (solution.maxSubArray(test_case.input) == test_case.output) {
      cout << "test_case[" << case_index << "] is pass." << endl;
    } else {
      cout << "test_case[" << case_index << "] is fail." << endl;
    }
    ++case_index;
  }

  return EXIT_SUCCESS;
}

## Result

Runtime: 12 ms, faster than 78.72% of C++ online submissions for Maximum Subarray.
Memory Usage: 13.4 MB, less than 17.60% of C++ online submissions for Maximum Subarray.

###### tags: `LeetCode-Easy` `C++`