CodeWars 여섯 번째 문제

Maximum subarray sum

public class Max {
  public static int sequence(int[] arr) {
    if(arr.length == 0) {
      return 0;
    }
    
    if(arr.length == 1) {
      return arr[0];
    }
    
    int max = 0;
    int k = arr[0];
    
    for(int i = 0; i < arr.length -1; i++) {
      k = k + arr[i+1];
          
      if(k < arr[i+1]) {
        k = arr[i+1];
      }
      
      if(max < k) {
        max = k;
      }
    }
    
    return max;
  }
}

*하 이거 영어 실력이 딸리니 알고리즘 이해도 부족… 어쨌든

*구글 검색으로 찾아보니 Kadane 알고리즘이라는 유명한 문제라더라.

*Kadane 알고리즘

예시1)

-2, 1, -3, 4, -1, 2, 1, -5, 4

-2, 1, -2, 4, 3, 5, 6, 1, 5

예시2)

10, -4, 3, 1, 5, 6, -35, 12, 21, -1

10, 6, 9, 10, 15, 21, -14, 12, 33, 32