LeetCode DayGreedy-Algorithmus Teil 1

    public int findContentChildren(int[] g, int[] s) {
        // avoid null pointer
        if(g.length == 0 || s.length ==0){
            return 0;
        }
        // 2 * nlogn
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            } else{
                j++;
            }
        }
        return count;   
    }

    int j = 0;
    int count = 0;
    for(int i=0; i<s.length && j<g.length; i++){
        if(s[i] >= g[j]){
            j++;
            count++;
        }
    }
    return count;   
}


</p>
<p>`</p>

<h2>
  
  
  376. Wiggle-Folge
</h2>

<p>Eine Wackelsequenz ist eine Sequenz, bei der die Unterschiede zwischen aufeinanderfolgenden Zahlen streng zwischen positiv und negativ wechseln. Der erste Unterschied (falls vorhanden) kann entweder positiv oder negativ sein. Eine Folge mit einem Element und eine Folge mit zwei ungleichen Elementen sind trivialerweise Wiggle-Folgen.</p>

<p>Zum Beispiel ist [1, 7, 4, 9, 2, 5] eine Wackelsequenz, da die Differenzen (6, -3, 5, -7, 3) zwischen positiv und negativ wechseln.<br>
Im Gegensatz dazu sind [1, 4, 7, 2, 5] und [1, 7, 4, 5, 5] keine Wiggle-Sequenzen. Das erste liegt nicht daran, dass die ersten beiden Differenzen positiv sind, und das zweite nicht daran, dass die letzte Differenz Null ist.<br>
Eine Teilsequenz wird erhalten, indem einige Elemente (möglicherweise Null) aus der Originalsequenz gelöscht werden und die übrigen Elemente in ihrer ursprünglichen Reihenfolge belassen werden.</p>

<p>Gibt bei einem gegebenen ganzzahligen Array „nums“ die Länge der längsten Wiggle-Teilfolge von „nums“ zurück.</p>

<p>Beispiel 1:</p>

<p>Eingabe: nums = [1,7,4,9,2,5]<br>
Ausgabe: 6<br>
Erläuterung: Die gesamte Sequenz ist eine Wackelsequenz mit Unterschieden (6, -3, 5, -7, 3).<br>
Beispiel 2:</p>

<p>Eingabe: nums = [1,17,5,10,13,15,10,5,16,8]<br>
Ausgabe: 7<br>
Erläuterung: Es gibt mehrere Teilsequenzen, die diese Länge erreichen.<br>
Eine davon ist [1, 17, 10, 13, 10, 16, 8] mit Unterschieden (16, -7, 3, -3, 6, -8).<br>
Beispiel 3:</p>

<p>Eingabe: nums = [1,2,3,4,5,6,7,8,9]<br>
Ausgabe: 2</p>

<p>Einschränkungen:</p>

<p>1 <= nums.length <= 1000<br>
0 <= nums[i] <= 1000</p>

<p>Nachfassen: Konnten Sie das Problem in O(n) Zeit lösen?</p>

<p>`<br>
    public int wiggleMaxLength(int[] nums) {<br>
        if(nums.length == 0){<br>
            return 0;<br>
        }<br>
        int count = 1;<br>
        int preFlag = 0;<br>
        int pre = nums[0];</p>

<pre class="brush:php;toolbar:false">    for(int i=1; i<nums.length; i++){
        if(nums[i]-nums[i-1] != 0){
            int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);

            if(flag == -preFlag || preFlag == 0){
                preFlag = flag;
                count++;
            }
        }
    }
    return count;
}

            }
            max = Math.max(max, sum);
        }else{
            if(sum<0){
                sum = nums[i];
            }else{
            sum += nums[i];
            }
            max = Math.max(max, sum);
        }
    }
    return max;

}

            }
            max = Math.max(max, sum);
    }
    return max;

}

    int sum = 0;
    for(int i=0; i<nums.length; i++){
        sum+= nums[i];
        if(max < sum){
            max = sum;
        }
        if(sum <0){
            sum = 0;
        }
            // if(sum < 0){
            //     sum = nums[i];
            // }else{
            //     sum += nums[i];

            // }
            // max = Math.max(max, sum);

    }
    return max;

}