# LeetCode : 0053. Maximum Subarray (array)
###### tags:`leetcode`

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class BaseSolution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sunarry = INT_MIN;
        for (int i = 0 ; i < nums.size();i++){
            int current_array = 0;
            // clear next run subarray Value.
            for(int j = i ; j < nums.size(); j++){
                current_array +=nums[j];
                //check subarry is max or not
                max_sunarry = max(max_sunarry,current_array);
            }
        }
        return max_sunarry;
    }
    //time complexity O(N^2)
    //space complexity O(1)
};

int main(void)
{
    BaseVectorPrint printVector;
    BaseSolution runfunc;

    vector<int> test01 = {  -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    vector<int> test02 = {  1 };
    vector<int> test03 = {  5, 4, -1, 7, 8 };
    vector<int> ans ;

    ans = runfunc.maxSubArray(test01);
    //printVector.BasePrint00(ans);
    printf("and = %d\n", ans);

    //printf("%d\n",input_Nums);
    printf("test\n");
    system("pause");
}