class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> result;
        for(int i = 1; i<=n; i++)
        {
            if(i%3 == 0 and i%5 ==0)
            {
                result.push_back("FizzBuzz");
            }
            else if(i%3 == 0 )
            {
                result.push_back("Fizz");
            }
            else if(i%5 == 0)
            {
                result.push_back("Buzz");
            }
            else
            {
                string tem = to_string(i);
                result.push_back(tem);
            }
        }
        return result;

    }
};

class MinStack {
public:
    /** initialize your data structure here. * /
    vector<int> a;
    vector<int> min;
    MinStack() {
        min.push_back(2147483647);
    }

    void push(int x) {
        a.push_back(x);
        if(x<min.back())
        {
            min.push_back(x);
        }
        else
        {
            min.push_back(min.back());
        }

    }

    void pop() {
        a.pop_back();
        min.pop_back();

    }

    int top() {
        return a.back();

    }

    int getMin() {
        return min.back();

    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class Solution {
    vector<int> arr, idx;
public:
    Solution(vector<int>& nums) {
        srand(time(NULL)); // generate random
        arr.resize(nums.size());
        idx.resize(nums.size());
        for(int i = 0; i<nums.size();i++)
        {
            arr[i] = nums[i];
            idx[i] = nums[i];
        }

    }

    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        for(int i = 0; i<arr.size();i++)
        {
            arr[i] = idx[i];
        }
        return arr;

    }

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int i,j;
        for(i = arr.size() -1; i>0; i--)
        {
            j = rand() % (i+1); // 0,1,2중으로 계속 나오는 것
            swap(arr[i],arr[j]); // 0,1,2 어레이중의 데이터를 스왑하는 것 랜덤적으로
        }
        return arr;

    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        if (n==0) return 0;
        if (n==1) return nums[0];
        if (n==2) return max(nums[0],nums[1]);
        vector<int> f(n,0);
        f[0] = nums[0];
        f[1] = max(nums[0],nums[1]);
        for(int i = 2; i<n; i++)
        {
            f[i] = max(f[i-2]+nums[i],f[i-1]);
        }
        return f[n-1];

    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        else if (nums.size() == 1) return nums.at(0);

        int int_local_max = nums.at(0);
        int int_global_max = nums.at(0);
        int sz_length  = nums.size();
        for (int i = 1; i < sz_length; i++) {
            int_local_max  = max(int_local_max + nums.at(i), nums.at(i));
            int_global_max = max(int_local_max, int_global_max);
        }

        return int_global_max;
    }
};

sum=max(sum,0); // prev step
sum+=A[i];