LeetCode DayGreedy 알고리즘 2부

    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = Integer.MAX_VALUE;
        int sum = 0;
        int peek = 0;

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if(num > buy && num > peek){
                profit = num - buy;
                peek = num;
            }
            else if((num>buy && num<peek) || num < buy){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }

        return sum+profit;
    }

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }
        int profit = 0;
        int buy = prices[0];
        int sum = 0;
        int peek = prices[0];

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if( num > peek){
                profit = num - buy;
                peek = num;
            }
            else if(num<peek){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }
        sum += profit;
        return sum;
    }

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int change = nums[nums.length-1] >=0?0:nums.length-1;
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0 && k>0){

                sum  -= nums[i];
                k--;
            }else{
                sum += nums[i];
            }
            // find the cross over 
            if(i>0 && nums[i-1]<=0 && nums[i]>0){
                if(-nums[i-1]>nums[i]){
                    change = i;
                }else{
                    change = i-1;
                }    
            }  
        }
        // k>nums.length so we need to run out of these k
        if(k>0){
            if(k%2!=0){
                //find the min abs value
                sum -= 2*Math.abs(nums[change]);
            }
        }
        return sum;
    }




</p>
<h2>
  
  
  55. 점프 게임
</h2>

<p>정수 배열 nums가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.</p>

<p>마지막 인덱스에 도달할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.</p>

<p>예 1:</p>

<p>입력: 숫자 = [2,3,1,1,4]<br>
출력: true<br>
설명: 인덱스 0에서 1로 1단계 점프한 다음 마지막 인덱스로 3단계 점프합니다.<br>
예시 2:</p>

<p>입력: 숫자 = [3,2,1,0,4]<br>
출력: 거짓<br>
설명: 무슨 일이 있어도 항상 인덱스 3에 도착합니다. 최대 점프 길이는 0이므로 마지막 인덱스에 도달할 수 없습니다.</p>

<p>제약사항:</p>

<p>1 <= nums.length <= 10^4<br>
0 <= 숫자[i] <= 10^5</p>
<h2>
  
  
  잘못된 코드
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        //find whether achive the last element so that we only can see whether can reach the second last element 
        for(int i=0; i<nums.length-1;){
            int size = nums[i];
            int next = 0;
            int nextVal = 0;
            if(size == 0){
                return false;
            }
            if(i+size >= nums.length){
                return true;
            }
            //find the max steps among the current step
            for(int j=0; j<=size; j++){
                // calculate max for both index and value
                if(i+j+nums[i+j]>next){
                    next = i+j+nums[i+j];
                }
            }
            i = next;
        }
        return true;
    }


</p>
<h2>
  
  
  잘못된 코드 2
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        if(nums.length==1){

            return true;
        }

        if(nums[0] == 0){
            return false;
        }

        for(int i=0; i<nums.length-1; i++){
            if(i+nums[i]>=nums.length-1){
                return true;
            }
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        if(nums.length==1){      
            return true;
        }

        int range = 0;

        for(int i=0; i<=range; i++){
            range = Math.max(range, i+nums[i]);
            if(range >= nums.length-1){
                return true;
            }
        }

        return false;
    }