数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 中最大环形子数组和
给定一个数组，任务是形成子数组，使得子数组以循环方式相加的结果为最大值。
输入 − int arr[] = {1, 2, 8, 4, 3, 0, 7}
输出 − 最大环形子数组和为：22
解释 − 给定数组 {1, 2, 8, 4, 3, 0, 7}，其最大和子数组为 7 + 1 + 2 + 8 + 4 = 22。
输入 − int arr[] = { 2, 5, -1, 6, 9, 4, -5 }
输出 − 最大环形子数组和为：25
解释 − 给定数组 {2, 5, -1, 6, 9, 4, -5}，其最大和子数组为 4 + 2 + 5 - 1 + 6 + 9 = 25。
下面程序中使用的方案如下：
输入一个包含正负值的整数数组。
计算数组大小。
将数组和大小传递给函数进行进一步处理。
创建一个临时变量 total 并将其设置为 0
从 i = 0 开始循环到数组大小
在循环内，将 total 设置为 total + arr[i]
设置 temp = arr[0], temp_2 = arr[0], temp_3 = arr[0], temp_4 = arr[0]
从 i = 1 开始循环到数组大小
在循环内设置 temp = max(temp + arr[i], arr[i]), temp_2 = max(temp_2, temp), temp_3 = min(temp_3 + arr[i], arr[i]), temp_4 = min(temp_4, temp_3)
检查 IF size == 1 则返回 arr[0]
检查 IF temp_4 == total 则返回 temp_2
设置 max_sum = max(temp_3, total - temp_4)
返回 max_sum
打印结果。
示例
#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
int total = 0;
for (int i = 0; i < size; i++){
total += arr[i];
}
int temp = arr[0];
int temp_2 = arr[0];
int temp_3 = arr[0];
int temp_4 = arr[0];
for (int i = 1; i < size; i++){
temp = max(temp + arr[i], arr[i]);
temp_2 = max(temp_2, temp);
temp_3 = min(temp_3 + arr[i], arr[i]);
temp_4 = min(temp_4, temp_3);
}
if (size == 1){
return arr[0];
}
if (temp_4 == total){
return temp_2;
}
int max_sum = max(temp_3, total - temp_4);
return max_sum;
}
int main(){
int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
return 0;
}输出
如果运行以上代码，将生成以下输出：
Maximum circular subarray sum is: 25
282 次查看
