Page tree
Skip to end of metadata
Go to start of metadata
  1. time out
    		int max = nums[0];
            for (long i = 0; i < nums.length; i++) {
    
                for (long j = 1; j <= nums.length - i; j++) {
                    final int value = Arrays.stream(nums)
                            .boxed()
                            .mapToInt(Integer::intValue)
                            .skip(i)
                            .limit(j)
                            .sum();
    
                    if (value > max) {
                        max = value;
                    }
                }
            }
    		return max;


    회고 (*참고 자료 : [카데인 알고리즘] https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29)

    		public int maxSubArray(int[] nums) {
            /**
             * sum(nums[i-1]) + num[i], num[i]
             */
            for (int i = 1; i < nums.length; i++) {
                nums[i] = Math.max(nums[i], nums[i - 1] + nums[i]);
            }
            return Arrays.stream(nums)
                    .max()
                    .getAsInt();
        }
  2. 회고 [dp의 작은 문제 찾기 : (n 번째 계단을 오르는 경우) = (n-1 번째 계단을 오르는 경우) + (n-2 번째 계단을 오르는 경우)]

    public int climbStairs(int n) {
            if (n < 3) {
                return n;
            }
    
            int[] ways = new int[n + 1];
            ways[1] = 1;
            ways[2] = 2;
    
            for (int i = 3; i <= n; i++) {
                ways[i] = ways[i - 1] + ways[i - 2];
            }
            return ways[n];
        }
  3. 회고 (실패.. 다시 도전 중)

    public int rob(int[] nums) {
    
            if (nums.length == 0) {
                return 0;
            }
    
            if (nums.length == 1) {
                return nums[0];
            }
    
            if (nums.length < 3) {
                return Math.max(nums[0], nums[1]);
            }
    
            for (int i = 2; i < nums.length; i++) {
                nums[i] = nums[i] + nums[i - 2];
            }
    
            return Math.max(nums[nums.length - 1], nums[nums.length - 2]);
        }
  • No labels