LeetCode Maximum_Subarray

LeetCode Maximum_Subarray

2021, Mar 09    

문제

  • Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

leetcode-maximum-subarray

내가 푼 알고리즘.

  • 항상 위와 같은 문제를 보면 모든 배열을 탐색해서 더해보는 방법이 제일 먼저 떠오른다. 더 나은 방법이 있겠지만.. 우선은 실전이다 생각하고 제일 빠르게 생각난 방법으로 문제를 풀어보았다.
  • 인텔리제이에서 문제를 풀고, 옮겨서 테스트를 해보는 방식으로 진행했다.

        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int answer = -2147483648; //int의 최소값
        
        if (nums.length == 1){
            return nums[0];
        }
            
        for(int i = 0 ; i < nums.length ; i++){
            int temp = 0;
            for(int j = i ; j < nums.length ; j ++){
                temp = temp + nums[j];
                if(answer < temp){
                    answer = temp;
                }
            }
        }
  • 위의 코드로 문제를 풀어내면..풀리기야 하겠지만..속도가 느리다 .
  • 이유는 최악의 경우 전체 경우의 수를 전부 탐색하기 때문이다.
  • Runtime: 98 ms, faster than 6.94% of Java online submissions for Maximum Subarray.
  • Memory Usage: 38.9 MB, less than 58.18% of Java online submissions for Maximum Subarray.
  • 속도가 느리다는 것을 알 수 있다.

참고한 알고리즘.


    	int currentSum = nums[0];
    	int maxSum = nums[0];
    	
    	for(int i=1; i<nums.length; i++) {
    		currentSum = Math.max(nums[i]+currentSum, nums[i]);
    		maxSum = Math.max(currentSum, maxSum);
    	}
    	
    	return maxSum;
  • 참고한 코드로 문제를 돌려보면 for문을 1회 실행하기 때문에 시간복잡도는 O(n)이 됨을 알 수 있다. 크…
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Maximum Subarray.
  • Memory Usage: 38.6 MB, less than 91.05% of Java online submissions for Maximum Subarray.
# leetCode # algorithm