[Leetcode][53. Maximum Subarray] 53. Maximum Subarray 코딩 인터뷰 문제풀이 Java

53. Maximum Subarray 문제풀이

Maximum Subarray - LeetCode

난이도는 Easy. 굉장히 흔히 볼 수 있고 접할 수 있는 문제라고 생각한다. 항상 (적어도 미국에선) 코딩인터뷰에서 중요한건, 문제를 다 풀고 아니고가 아니라, 이 사람이 어떻게 "생각"하는지를 보는 것 같습니다. 결국 코딩으로 완벽한 답을 못해낼지언정, 이 사람이 문제에대해 어떻게 접근하는지를 보고싶어하기에, 항상 코딩으로 바로 넘어가지 말고 1) 문제를 제대로 이해했는지를 물어봐 주세요 2) edge cases에 대해 생각해보고 그럴땐 어떻게 하기를 원하는지를 인터뷰이한테 물어봐 주세요 3) 먼저 optimal한 방법이 뭔지를 모르겠다면, 짧게라도 간결하게 brute-force방법을 설명하고 말해주면 좋습니다 4) 그리고 일단 입으로 (말로) 내가 어떻게 생각하고 있는지를 설명해 주세요.  

 

그 이후로는, 솔직히 인터뷰이-인터뷰어 간의 티키타카가 잘 되는지가 중요합니다. 인터뷰어도 가만히 있는 사람이 아니라, 어느정도 준비된 사람이여야지만 대화를 충분히 끌어내고 더불어 인터뷰이의 포텐셜까지 끌어내서 그 사람이 충분한 힌트는 얻되, 충분히 그 사람이 문제를 해결할 수 있는지 없는지를 판단할 수 있기 때문입니다. 동시에 인터뷰이도 준비가 어느정도 되어있는 사람이여야지만 그 대화가운데서 인터뷰어가 준 힌트를 이해하고 대화와 질문을 적절히 섞어가면서 그 대화를 이끌어나갈 수 있기때문입니다. 결론은.. 준비가 안되면 불가능하다ㅎㅎ 그렇기에 꾸준히 이렇게 문제를 다시한번 보는것도 좋은 것 같습니다! 

 

 public int maxSubArray(int[] nums) {
 
   if(nums.length == 1) return nums[0];
   /* NEED TO THINK; What if in the middle of the project, we have investigated that some
   * unwanted nums have been passed through the argument? We might need to take care of
   * how to deal with those cases - like are we going to retry? or throw exception, or
   * assign some certain value to identify that was unwated value. 
   */
   int maxValue = Integer.MIN_VALUE;
        
        
   int currentSubarray = nums[0];
   int maxSubarray = nums[0];
   for (int i = 1; i < nums.length; i++) {
      int num = nums[i];
      // If current_subarray is negative, throw it away. Otherwise, keep adding to it.
      currentSubarray = Math.max(num, currentSubarray + num);
      maxSubarray = Math.max(maxSubarray, currentSubarray);
    }
   return maxSubarray;
}

 

* Time complexity: O(N) - to compute currentSubarray and maxSubarray, needed to go through all elements from the nums array

* Space complexity: O(1) - there is no used extra space