MaximumSubArray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

 

• 기본 합산 값과 대비해서 다른 원소들의 합산 값을 max 로 비교
• 마지막 수에 대한 고려가 없으므로 마지막 수 비교.

private static int solve(int[] nums) {
		int max = 0;
		for(int i=0; i<nums.length; i++) {
			int sum = 0;// 합계는 매 원소가 올때마다 초기화되어야함
			sum = nums[i];//첫 수 대입
			for(int j=i +1; j<nums.length; j++) {
				sum = sum + nums[j];
				max = Math.max(max, sum);
			}
		}
		
		//마지막 수 고려
		max = Math.max(max, nums[nums.length-1]);
		
		return max;
		
	}

---

풀이

 

• 첫 원소의 부가 배열이나 max 치는 전부 첫 원소 이므로 첫원소는 그대로 대입해주면된다.
• 기존 원소와 배열의 합산 값을 비교 함
• max 치와 비교함

시작부터 구할 수 있는 가장 큰 수를 구하고, 순환 원소와 합산하거나, 순환원소보다 작은지 확인

순환원소가 크다면 자연스럽게 시작 수는 순환원소가 됨 그 이후에 다음 순환원소와 합산.

//모든 배열들의 원소 합 중 가장 큰 수를 구해야함
	private static int solve(int[] nums) {
		 
		// 알고리즘의 처음은 언제나 그릇
		int max = 0;
		int sum = 0;
		
		// 첫 원소는 max 치 합산, 서브 배열 치 는 전부 첫원소로 떨어짐
		sum = nums[0];
		max = nums[0];
		
		for(int i=1; i<nums.length; i++) {
			// 첫 원소의 서브배열은 구했으니, 다음 원소나, 다음 원소와 나머지 원소의 합산 값 을 검토해야함.
			sum = Math.max(nums[i], sum + nums[i]);
			// max 와 비교
			max = Math.max(sum, max);
		}
		
		return max;
	}