leetcode) #53. Maximum Subarray

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

 

for 루프로 간단하게 푼 것

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
    int ans = 0;

    if(len == 1) return nums[0];

    int sum = 0; bool trig = false;
    for(int i = 0; i < len; i++) {
        sum = 0;
        for(int j = i; j < len; j++) {
            sum += nums[j];
            if(!trig) { ans = sum; trig = true; }
            ans = max(sum, ans);
        }
    }
    return ans;
    }
};

 

for문에서 i값 증가되면서, nums[i]와 이전값들의 합 비교.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int allmax = -100000000;
    	int cur_max = -100000000;

    		for(int i = 0; i < nums.size(); i++) {
        		cur_max = max(nums[i], cur_max + nums[i]);
        		allmax = max(allmax, cur_max);

    		}

    	return allmax;
    }
};

처음에 allmax값과 cur_max값을 numeric_limits<int>::min()로 int의 최솟값으로 설정했는데, 

cur_max + nums[i]를 하니까 int의 값의 범위를 벗어 나서 그런지 음수값 + 음수값을 했는데 양수가 나왔다.

따라서 그냥 -10억으로 수정.