本文共 1563 字，大约阅读时间需要 5 分钟。

题目

Given an array of integers of size ‘n’.Our aim is to calculate the maximum sum of ‘k’ consecutive elements in the array.Input  : arr[] = {100, 200, 300, 400}         k = 2Output : 700Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}         k = 4 Output : 39We get maximum sum by adding subarray {4, 2, 10, 23}of size 4.Input  : arr[] = {2, 3}         k = 3Output : InvalidThere is no subarray of size 3 as size of wholearray is 2.

我的尝试

我想到了滑动窗口对移动，如上图所示，但是我不知道如何去计算每个窗口对和？如果窗口内部用for循环处理，岂不是不能O（n）实现了，后来看了解法，发现窗口的和值，是通过“增加-删除”实现的。比如第一个 窗口是2，3，5.计算出第一个窗口的sum。第二个窗口发生变化，增加6，减去2，在sum基础上增加6，减去2，计算出新的sum并且比较出最大的sum

解法

// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG { 	// Returns maximum sum in 	// a subarray of size k. 	static int maxSum(int arr[], int n, int k) 	{ 		// k must be greater 		if (n < k) 		{ 		System.out.println("Invalid"); 		return -1; 		} 			// Compute sum of first window of size k 		int max_sum = 0; 		for (int i = 0; i < k; i++) 		max_sum += arr[i]; 			// Compute sums of remaining windows by 		// removing first element of previous 		// window and adding last element of 		// current window. 		int window_sum = max_sum; 		for (int i = k; i < n; i++) 		{ 		window_sum += arr[i] - arr[i - k]; 		max_sum = Math.max(max_sum, window_sum); 		} 			return max_sum; 	} 		// Driver code 	public static void main(String[] args) 	{ 		int arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20}; 		int k = 4; 		int n = arr.length; 		System.out.println(maxSum(arr, n, k)); 	} } // This code is contributed // by prerna saini.

转载地址：https://kerry.blog.csdn.net/article/details/83184414 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！